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

location: ProblemsDescription / GraphColouring

Graph Colouring

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.

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).

For example:

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 Format

The initial facts and a set of choosenColour predicates, one for each node, specifying the node's colour. Continuing the example:

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

Example

Calibration

The Two Possible Values of the Chromatic Number of a Random Graph (with A. Naor) Annals of Mathematics, 162 (3), (2005), 1333-1349. http://www.cs.ucsc.edu/~optas/papers/kcol.pdf

Suggests that given a random graph with n nodes and a density of (d/n) then the chromatic number is either k or k+1 where k is the smallest number such that d < 2k log(k).

Thus settings with around 125-150 nodes (135 is good), link density of 0.1 (d = 12-15) and 5 colours gives difficult programs.

Comment

This problem was part of the Second ASP Competition and was proposed by Martin Brain.

Author(s)