Source : Free On-Line Dictionary of Computing

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