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

See also four colour map theorem.

This article is provided by FOLDOC - Free Online Dictionary of Computing (

**foldoc.org**)Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: