graph colouring

graph colouring

(application)A constraint-satisfaction problem often usedas a test case in research, which also turns out to beequivalent to certain real-world problems (e.g. register allocation). Given a connected graph and a fixed number ofcolours, the problem is to assign a colour to each node,subject to the constraint that any two connected nodes cannotbe assigned the same colour. This is an example of anNP-complete problem.

See also four colour map theorem.