# 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.

How to Cite This Entry:
Graph colouring. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_colouring&oldid=47127
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article