|
|
|
|
chromatic number
|
(Definition)
|
|
|
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.
|
"chromatic number" is owned by mathcam. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
Cross-references: NP-hard, colouring, vertices, complete graph, isomorphic, subgraph, contains, clear, colours, number, graph
There are 12 references to this entry.
This is version 5 of chromatic number, born on 2002-02-03, modified 2004-04-13.
Object id is 1764, canonical name is ChromaticNumber.
Accessed 7405 times total.
Classification:
| AMS MSC: | 05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[r] & {\co... ... \ar@{-}[dl] \ & {\color{green}D} \ar@{-}[r] & {\color{blue}E} & } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1764/l2h/img1.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[r] & {\co... ... \ar@{-}[dl] \ & {\color{green}D} \ar@{-}[r] & {\color{blue}E} & } } \end{xy}$")