welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

Revision 2 as of 2012-11-06 16:35:35

location: GraphColouring

Graph Colouring

Contents

  1. Graph Colouring
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Problem Peculiarities
    7. Notes and updates
    8. Author(s)

Problem Description

A graph is a set of nodes and a symmetric, binary link relation on nodes. Given a set of N colours, a graph is colourable if each node can be assigned a colour in such a way that any two nodes that are linked together cannot have the same colour.

Predicates

Input format

A number of node facts which give the names of the nodes. Node names are consecutive, ascending integers starting from 1.

A number of colour facts which give the names of the colours. Colour names start with the sequence "red", "green", "blue".

A number of link facts which say which nodes are linked. Note that if link(N1,N2). is included then so will link(N2,N1).

Output format

A set of choosenColour predicates, one for each node, specifying the node's colour.

Example(s)

Input: node(1). node(2). node(3). link(1,2). link(2,1). link(2,3). link(3,2). link(3,1). link(1,3). colour(red). colour(green). colour(blue).

Output: chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).

Problem Peculiarities

Type: Search Competition: System Track Complexity: NP-complete

Notes and updates

Instances taken from last competition (60 instances).

Author(s)