chromatic number


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

Consider the following graph:

\xymatrixA\ar@-[r]&B\ar@-[r]\ar@-[d]&C\ar@-[r]\ar@-[dl]&F\ar@-[dl]&D\ar@-[r]&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 subgraphMathworldPlanetmath (BCD) that is isomorphic to the complete graphMathworldPlanetmath 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