chromatic number
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 colours. Furthermore, it’s clear that it cannot be coloured with fewer than colours, as well: it contains a subgraph () that is isomorphic to the complete graph of vertices. As a result, the chromatic number of this graph is indeed .
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 |