chromatic number (original) (raw)

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

Consider the following graph:

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.