View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449002.png" />-colourable if there exists a regular vertex colouring of the graph by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449003.png" /> colours. The smallest number of colours which suffices for a regular vertex colouring of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449004.png" /> is called the chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449005.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449006.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449007.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g0449008.png" /> is said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490010.png" />-chromatic. A graph is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490011.png" />-chromatic if and only if it contains no simple cycles of odd length. If the maximum degree of the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490012.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490014.png" /> is always <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490015.png" />-colourable except in two cases: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490017.png" /> has a connected component which is a cycle of odd length; or 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490018.png" /> and the complete graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490019.png" /> vertices is a connected component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490020.png" />.

The following inequality is valid for the union of two graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490022.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490023.png" /></td> </tr></table>

equality being attainable. Moreover, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490024.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490025.png" />, then there exist subgraphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490027.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490028.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490031.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490032.png" /> is a graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490033.png" /> vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490034.png" /> is the complementary graph to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490035.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490036.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490037.png" /></td> </tr></table>

all the bounds being attainable. The chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490038.png" /> of a two-dimensional surface <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490039.png" /> is the largest of the chromatic numbers of the graphs which can be regularly imbedded in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490040.png" /> (cf. [[Graph imbedding|Graph imbedding]]). The equality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490041.png" /></td> </tr></table>

is valid for an orientable surface <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490042.png" /> of genus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490043.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490044.png" />, this equation assumes the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490045.png" />, which is the statement of the [[Four-colour problem|four-colour problem]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490046.png" /> be the number of different regular colourings of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490047.png" /> with numbered vertices with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490048.png" /> or fewer colours; then, for any graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490049.png" />, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490050.png" /> is a polynomial in the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490051.png" />, called the chromatic polynomial of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490052.png" />. Thus, the chromatic polynomial of any tree with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490053.png" /> vertices has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490054.png" />. The edge chromatic number (chromatic class) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490055.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490056.png" /> is the smallest number of colours sufficient for a regular colouring of the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490057.png" />. If the maximum degree of the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490058.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490059.png" /> (multiple edges are permitted), then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490060.png" /></td> </tr></table>

If, in addition, the multiplicity of each edge is at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490061.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490062.png" />. In particular, for graphs without loops or multiple edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044900/g04490063.png" />.

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

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



====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|Graph, planar]]). Recent surveys on edge colourings are [[#References|[a1]]] and [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Fiorini,   R.J. Wilson,   "Edge-colourings of graphs" , Pitman  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.J. Wilson,   "Introduction to graph theory" , Longman  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.C. Read,   "An introduction to chromatic polynomials"  ''J. Comb. Theory'' , '''4'''  (1968)  pp. 52–71</TD></TR></table>