# Encoding graph-coloring_decision.gringo

Name graph-coloring_decision.gringo [Root]    Graph Problems (32) Martin Gebser Martin Gebser and Roland Kaminski 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 ----- 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 ------ 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). 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. Author: Martin Brain 2009-03-27 12:58 2009-03-27 12:58 Color Group 1 colour/1link/2node/1 chosenColour/2colour/1link/2node/1 No ASP Contest 09 (Martin Gebser) 1 { chosenColour(N,C) : colour(C) } 1 :- node(N). :- link(U,V), U < V, chosenColour(U,C), chosenColour(V,C).