PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
chromatic number (Definition)

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

Consider the following graph:

$$\xymatrix{ {\color{red}A} \ar@{-}[r] & {\color{blue}B} \ar@{-}[r] \ar@{-}[d] & {\color{red}C} \ar@{-}[r] \ar@{-}[dl] & {\color{green}F} \ar@{-}[dl] \\ & {\color{green}D} \ar@{-}[r] & {\color{blue}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 ($BCD$ 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.




"chromatic number" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:

See Also: chromatic number and girth, four-color conjecture, chromatic polynomial, chromatic number of a metric space

Log in to rate this entry.
(view current ratings)

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 8692 times total.

Classification:
AMS MSC05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)