chromatic number

The chromatic number of a graph is the minimum number of colours required to colour it.

Consider the following graph:

$\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}&}$

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 ( $B C D$ ) 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.

Title	chromatic number
Canonical name	ChromaticNumber
Date of creation	2013-05-16 21:23:44
Last modified on	2013-05-16 21:23:44
Owner	mathcam (2727)
Last modified by	unlord (1)
Numerical id	9
Author	mathcam (1)
Entry type	Definition
Classification	msc 05C15
Related topic	ChromaticNumberAndGirth
Related topic	FourColorConjecture
Related topic	ChromaticPolynomial
Related topic	ChromaticNumberOfASpace