= Graph Colouring =

<<TableOfContents>>

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

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

== Comment ==

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

== Author(s) ==
 * Author: Yuliya Lierler 	
   * Affiliation: University of Kentucky, USA
 * Author: Marcello Balduccini 
   * Affiliation: Kodak Research Labs, USA