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

Title colouring problem ColouringProblem 2013-03-22 12:17:00 2013-03-22 12:17:00 vampyr (22) vampyr (22) 7 vampyr (22) Topic msc 05C15 coloring problem colour color graph colouring graph coloring