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.

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

Mentioned in

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.

A NNIA Scheme for Timetabling Problems

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.

The game colouring number of powers of forests

We apply these ideas to three problems: maximum matching, graph colouring and Kolmogorov complexity.

Cost-effectiveness of algorithms

Keywords: Graph theory graph colouring graph minors Hadwiger's conjecture.

A Weak form of Hadwiger's Conjecture

A number of commonly used strategies have been adopted from the graph colouring problem.

Review on the optimization methods of solving exam timetabling

Andrea Schaerf and Luca Di Gaspero [1], reduced the exam timetabling problem into a graph colouring problem.

Improving exam time tabling solution using tabu search

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

Cost-effectiveness of algorithms

Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 32:547-556, 2004.

An exact algorithm for the generalized list T-coloring problem

All of the above graph colouring parameters have natural list generalizations.

Sequence variations of the 1-2-3 conjecture and irregularity strength

Graph Colouring Problems, chapter 4.9, pages 86-89.

Strong oriented chromatic number of planar graphs without short cycles

The subject of topological obstructions to graph colourings was started when Lovasz determined the chromatic numbers of Kneser graphs in Lovasz (1978).

The equivariant topology of stable Kneser graphs