= Graph Colouring =

<<TableOfContents>>

== Problem Description ==

* Input Predicates: node/1, link/2, colour/1

* Output Predicates: chosenColour/2

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.

== Input ==

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). <<BR>>
node(2). <<BR>>
node(3). <<BR>>
link(1,2). <<BR>>
link(2,1). <<BR>>
link(2,3). <<BR>>
link(3,2). <<BR>>
link(3,1). <<BR>>
link(1,3). <<BR>>
colour(red). <<BR>>
colour(green). <<BR>>
colour(blue). <<BR>>

== 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). <<BR>>
chosenColour(2,green). <<BR>>
chosenColour(3,blue). <<BR>>

== Calibration ==

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

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.

./graphGenerator.pl --nodes=$N --density=$D --colours=$C