colouring problem

The colouring problem is to assign a colour to every vertex of a graph such that no two adjacent vertices have the same colour. These colours, of course, are not necessarily colours in the optic sense.

Consider the following graph:

\\xymatrix{A\\ar@{-}[r]&B\\ar@{-}[r]\\ar@{-}[d]&C\\ar@{-}[r]\\ar@{-}[dl]&F\\ar@{-}[dl%]\\\\&D\\ar@{-}[r]&E&}

One potential colouring of this graph is:

\\xymatrix{{\\color[rgb]{1,0,0}A}\\ar@{-}[r]&{\\color[rgb]{0,0,1}B}\\ar@{-}[r]\\ar@{%-}[d]&{\\color[rgb]{1,0,0}C}\\ar@{-}[r]\\ar@{-}[dl]&{\\color[rgb]{0,1,0}F}\\ar@{-}[%dl]\\\\&{\\color[rgb]{0,1,0}D}\\ar@{-}[r]&{\\color[rgb]{0,0,1}E}&}

$A$ and $C$ have the same colour; $B$ and $E$ have a second colour; and $D$ and $F$ have another.

Graph colouring problems have many applications in such situations as scheduling and matching problems.