graph colouring

graph colouring

(application)
A constraint-satisfaction problem often used as a test case in research, which also turns out to be equivalent to certain real-world problems (e.g. register allocation). Given a connected graph and a fixed number of colours, the problem is to assign a colour to each node, subject to the constraint that any two connected nodes cannot be assigned the same colour. This is an example of an NP-complete problem.

See also four colour map theorem.
References in periodicals archive ?
A number of commonly used strategies have been adopted from the graph colouring problem.
implemented graph colouring techniques in the preparation of school timetables.
The use of Saturation Degree was first presented by Bfelaz (1979) for the graph colouring problem.
One of the earliest papers that applied this approach to the graph colouring problem was published by Wood (1969).
Two of the heuristics were based on graph colouring heuristics (LD and LCD); one was a random heuristic; and the remaining were specially designed heuristics that highlighted the two constraints that needed to be addressed (i.
A study by Costa and Hertz (1997) investigated the use of Ant Colony Optimisation in graph colouring problems in which they called their ant system ANTCOL.
In comparison to the best results in literature for the benchmark data sets, they obtained competitive results for the graph colouring problem and uncapacitated problem, while for the the capacitated problem they produced best results for several problem instances.
The subject of topological obstructions to graph colourings was started when Lovasz determined the chromatic numbers of Kneser graphs in Lovasz (1978).
A more systematic treatment of topological obstructions to the existence of graph colourings was suggested by Lovasz and started by Babson and Kozlov (2006).