welcome:
location: ProblemsDescription / GraphColouring

# 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.

## 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".

For example:

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

## Comment

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

## Author(s)

• Yuliya Lierler
• University of Kentucky, USA
• Marcello Balduccini
• Kodak Research Labs, USA

ASP Competition 2011: ProblemsDescription/GraphColouring (last edited 2011-01-10 10:24:56 by CarmenSantoro)