Graph colouring

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 $ k $- 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