chromatic number ChromaticNumber 2002-02-03 15:25:43 2004-04-13 11:41:07 Definition \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{xypic} \usepackage{color} The \emph{chromatic number} of a graph is the minimum number of colours required to colour it. Consider the following graph: $$\xymatrix{ {\color{red}A} \ar@{-}[r] & {\color{blue}B} \ar@{-}[r] \ar@{-}[d] & {\color{red}C} \ar@{-}[r] \ar@{-}[dl] & {\color{green}F} \ar@{-}[dl] \\ & {\color{green}D} \ar@{-}[r] & {\color{blue}E} & }$$ This graph has been coloured using $3$ colours. Furthermore, it's clear that it cannot be coloured with fewer than $3$ colours, as well: it contains a subgraph ($BCD$) that is isomorphic to the complete graph of $3$ vertices. As a result, the chromatic number of this graph is indeed $3$. This example was easy to solve by inspection. In general, however, finding the chromatic number of a large graph (and, similarly, an optimal colouring) is a very difficult (NP-hard) problem.