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 ?
Qu, "Roulette wheel graph colouring for solving examination timetabling problems," in Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications, vol.
Graph colouring considers the problem to assign colours to the vertices of a given graph in such a way that adjacent vertices receive distinct colours.
We apply these ideas to three problems: maximum matching, graph colouring and Kolmogorov complexity.
Keywords: Graph theory graph colouring graph minors Hadwiger's conjecture.
A number of commonly used strategies have been adopted from the graph colouring problem.
Andrea Schaerf and Luca Di Gaspero [1], reduced the exam timetabling problem into a graph colouring problem.
However, this is just 0 if there exists x [member of] [I.sub.n] such that [f.sub.0](x) = f (x), as might often occur (for example, in graph colouring, when x is a complete graph).
Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 32:547-556, 2004.
All of the above graph colouring parameters have natural list generalizations.
Graph Colouring Problems, chapter 4.9, pages 86-89.
The subject of topological obstructions to graph colourings was started when Lovasz determined the chromatic numbers of Kneser graphs in Lovasz (1978).