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