Namespaces
Variants
Actions

Difference between revisions of "Graph colouring"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
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" />.
+
<!--
 +
g0449002.png
 +
$#A+1 = 61 n = 0
 +
$#C+1 = 61 : ~/encyclopedia/old_files/data/G044/G.0404900 Graph colouring
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
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" />:
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<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>
+
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 $.
  
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
+
The following inequality is valid for the union of two graphs  $  G _ {1} $
 +
and $  G _ {2} $:
  
<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>
+
$$
 +
\chi ( G _ {1} \cup G _ {2} )  \leq  \
 +
\chi ( G _ {1} ) \chi ( G _ {2} ),
 +
$$
  
<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>
+
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
  
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
+
$$
 +
2 \sqrt {n }  \leq  \
 +
\chi ( G) + \chi ( \overline{G}\; )  \leq  n + 1,
 +
$$
  
<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>
+
$$
 +
n  \leq  \chi ( G) \chi ( \overline{G}\; )  \leq  \left (
 +
\frac{n + 1 }{2}
 +
\right )  ^ {2} ,
 +
$$
  
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
+
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|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/g04490060.png" /></td> </tr></table>
+
$$
 +
\chi ( S _  \gamma  )  = \
 +
\left [
  
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" />.
+
\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|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.
 
Problems involving graph colouring arise in design of communications, in radio-electronics, in planning of experiments, and in other fields.
Line 25: Line 115:
 
====References====
 
====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>
 
<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====
 
====Comments====

Revision as of 19:42, 5 June 2020


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