Namespaces
Variants
Actions

Graph colouring

From Encyclopedia of Mathematics
Jump to: navigation, search


An assignment of colours to the vertices and/or edges of a graph which displays certain properties. A regular vertex (edge) colouring is a colouring of the vertices (edges) of a graph in which any two adjacent vertices (edges) have different colours. A regular vertex colouring is often simply called a graph colouring. A graph is said to be - colourable if there exists a regular vertex colouring of the graph by k colours. The smallest number of colours which suffices for a regular vertex colouring of a graph G is called the chromatic number \chi ( G) of G . If \chi ( G) = k , G is said to be k - chromatic. A graph is 2 - chromatic if and only if it contains no simple cycles of odd length. If the maximum degree of the vertices of G is r , G is always r - colourable except in two cases: 1) r = 2 and G has a connected component which is a cycle of odd length; or 2) r > 2 and the complete graph with r + 1 vertices is a connected component of G .

The following inequality is valid for the union of two graphs G _ {1} and G _ {2} :

\chi ( G _ {1} \cup G _ {2} ) \leq \ \chi ( G _ {1} ) \chi ( G _ {2} ),

equality being attainable. Moreover, if G is such that \chi ( G) = k = a b , then there exist subgraphs G _ {1} and G _ {2} in G such that G = G _ {1} \cup G _ {2} , \chi ( G _ {1} ) = a , \chi ( G _ {2} ) = b . If G is a graph with n vertices and \overline{G}\; is the complementary graph to G , then

2 \sqrt {n } \leq \ \chi ( G) + \chi ( \overline{G}\; ) \leq n + 1,

n \leq \chi ( G) \chi ( \overline{G}\; ) \leq \left ( \frac{n + 1 }{2} \right ) ^ {2} ,

all the bounds being attainable. The chromatic number \chi ( S) of a two-dimensional surface S is the largest of the chromatic numbers of the graphs which can be regularly imbedded in S ( cf. Graph imbedding). The equality

\chi ( S _ \gamma ) = \ \left [ \frac{7 + \sqrt {1 + 48 \gamma } }{2} \right ]

is valid for an orientable surface S _ \gamma of genus \gamma > 0 . If \gamma = 0 , this equation assumes the form \chi ( S _ {0} ) = 4 , which is the statement of the four-colour problem. Let f ( G, t) be the number of different regular colourings of a graph G with numbered vertices with t or fewer colours; then, for any graph G , the function f ( G, t) is a polynomial in the variable t , called the chromatic polynomial of G . Thus, the chromatic polynomial of any tree with n vertices has the form f ( G, t) = {t ( t - 1) } ^ {n - 1 } . The edge chromatic number (chromatic class) \chi ^ \prime ( G) of G is the smallest number of colours sufficient for a regular colouring of the edges of G . If the maximum degree of the vertices of G is k ( multiple edges are permitted), then

k \leq \ \chi ^ \prime ( G) \leq \ \left [ { \frac{3}{2} } k \right ] .

If, in addition, the multiplicity of each edge is at most r , then \chi ^ \prime ( G) \leq k + r . In particular, for graphs without loops or multiple edges k \leq \chi ^ \prime ( G) \leq k + 1 .

Problems involving graph colouring arise in design of communications, in radio-electronics, in planning of experiments, and in other fields.

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2] O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)
[3] C.E. Shannon, "A theorem on colouring the lines of a network" J. Math. Phys. , 28 (1949) pp. 148–151

Comments

Besides vertex colourings and edge colourings, the colourings of the domains (faces) of a planar map have also been studied. The four-colour problem mentioned in the article above (which is now the four-colour theorem) originally belonged to this category (see Graph, planar). Recent surveys on edge colourings are [a1] and [a2].

References

[a1] S. Fiorini, R.J. Wilson, "Edge-colourings of graphs" , Pitman (1977)
[a2] S. Fiorini, R.J. Wilson, "Edge-colourings of graphs" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected Topics in Graph Theory , Acad. Press (1978) pp. Chapt. 5
[a3] R.J. Wilson, "Introduction to graph theory" , Longman (1985)
[a4] R.C. Read, "An introduction to chromatic polynomials" J. Comb. Theory , 4 (1968) pp. 52–71
How to Cite This Entry:
Graph colouring. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_colouring&oldid=52597
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article