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