|
|
|
|
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:
One potential colouring of this graph is:
 and  have the same colour;  and  have a second colour; and  and  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, applications, colouring, potential, adjacent vertices, graph, vertex
There are 32 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 12115 times total.
Classification:
| AMS MSC: | 05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\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}$](http://images.planetmath.org:8080/cache/objects/1758/l2h/img1.png "$\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}$")
![$\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/1758/l2h/img2.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}$")