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.

< Previous Terms Terms Containing graph colouring Next Terms >
Graph Algorithm and Software Package
graph coloring
constraint satisfaction
graph coloring
register allocation
Graphic ALGOL
Graphical Kernel System
Graphical User Interface
Graphic Display Interface
Graphic Language