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 -
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 |
Graph colouring. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_colouring&oldid=52597