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.
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).
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).
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).
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.
This problem was part of the Second ASP Competition and was proposed by Martin Brain.
- Yuliya Lierler
- University of Kentucky, USA
- Marcello Balduccini
- Kodak Research Labs, USA