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 ?
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.
2007), some more recent references concerning graph colouring games can be taken from Andres (2012) resp.
We apply these ideas to three problems: maximum matching, graph colouring and Kolmogorov complexity.
Keywords: optimisation, algorithms, cost-effectiveness, approximation algorithm, performance measure, graph colouring, matching, 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.
implemented graph colouring techniques in the preparation of school timetables.
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.
All of the above graph colouring parameters have natural list generalizations.
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).