graph coloring

from The Free On-line Dictionary of Computing (8 July 2008)

graph colouring
graph coloring

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