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
Canonical name	ColouringProblem
Date of creation	2013-03-22 12:17:00
Last modified on	2013-03-22 12:17:00
Owner	vampyr (22)
Last modified by	vampyr (22)
Numerical id	7
Author	vampyr (22)
Entry type	Topic
Classification	msc 05C15
Synonym	coloring problem
Synonym	colour
Synonym	color
Synonym	graph colouring
Synonym	graph coloring