You are here: irt.org | FOLDOC | 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.

Nearby terms: graph « Graph Algorithm and Software Package « graph coloring « **graph colouring** » Graphic ALGOL » Graphical Kernel System » Graphical User Interface

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL