The Wayback Machine - https://web.archive.org/web/20060925050450/http://planetmath.org/encyclopedia/ColouringProblem.html
PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
Main Menu
colouring problem (Topic)

The colouring problem is to assign a colour to every vertex of a graph such that no two adjacent vertices have the same colour. These colours, of course, are not necessarily colours in the optic sense.

Consider the following graph:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] \ar@... ... C \ar@{-}[r] \ar@{-}[dl] & F \ar@{-}[dl] \ & D \ar@{-}[r] & E & } } \end{xy}$

One potential colouring of this graph is:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[r] & {\co... ... \ar@{-}[dl] \ & {\color{green}D} \ar@{-}[r] & {\color{blue}E} & } } \end{xy}$

$ A$ and $ C$ have the same colour; $ B$ and $ E$ have a second colour; and $ D$ and $ F$ have another.

Graph colouring problems have many applications in such situations as scheduling and matching problems.



"colouring problem" is owned by vampyr.
(view preamble)


Other names:  coloring problem, colour, color, graph colouring, graph coloring

Cross-references: matching, colouring, potential, adjacent, graph, vertex
There are 23 references to this entry.

This is version 3 of colouring problem, born on 2002-02-03, modified 2002-02-04.
Object id is 1758, canonical name is ColouringProblem.
Accessed 7435 times total.

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

Pending Errata and Addenda
None.
Discussion
forum policy

No messages.

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