= 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 cannot have the same colour.

== Predicates ==

 * '''Input''': {{{node/1, link/2, colour/1}}}

 * '''Output''': {{{chosenColour/2}}}

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

Given the following 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).
}}}

Resulting in the output: 
{{{
chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).
}}}

Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/graph_colouring-sample.zip|download]]

== Problem Peculiarities ==

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

== Notes and updates ==

Instances taken from the 2009 competition (60 instances).

== Author(s) ==
 * Author: Johannes Wallner	
   * Affiliation: DBAI, Vienna University of Technology, Austria
 * Original Authors: Yuliya Lierler, Marcello Balduccini 
   * Affiliation: University of Kentucky and Kodak Research Labs