Namespaces
Variants
Actions

Difference between revisions of "Vizing theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200401.png" /> be a [[Graph|graph]] (assumed to be finite, undirected and loop-less), and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200402.png" /> be the maximum number of edges joining every pair of vertices. A simple graph will mean a graph without parallel edges. The chromatic index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200403.png" /> is the least number of colours needed to colour the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200404.png" /> in such a way that no two adjacent edges are assigned the same colour (cf. also [[Graph colouring|Graph colouring]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200405.png" /> is the maximum degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200406.png" />, then, obviously, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200407.png" />. The origins of chromatic graph theory may be traced back to 1852, with the birth of the [[Four-colour problem|four-colour problem]]. The first paper on edge colourings appeared 1880, when P.G. Tait [[#References|[a18]]] made the important observation that the four-colour conjecture is equivalent to the statement that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200408.png" />-regular planar graph has chromatic index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v1200409.png" />. But after this, little was done. In 1916, D. König [[#References|[a13]]] proved that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004010.png" /> is a bipartite graph (cf. also [[Graph, bipartite|Graph, bipartite]]), then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004011.png" />. The first non-trivial upper bound has been obtained by C.E. Shannon [[#References|[a17]]] in 1949, when he proved <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004012.png" /> for an arbitrary graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004013.png" />. The great breakthrough occurred in 1964, however, when V.G. Vizing [[#References|[a19]]] gave the following surprisingly strong result, now known as Vizing's theorem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004014.png" /> is a graph, then
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,  
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<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/v/v120/v120040/v12004015.png" /></td> </tr></table>
+
Out of 74 formulas, 74 were replaced by TEX code.-->
  
In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004016.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004017.png" /> is simple.
+
{{TEX|semi-auto}}{{TEX|done}}
 +
Let $G$ be a [[Graph|graph]] (assumed to be finite, undirected and loop-less), and let $\mu ( G )$ be the maximum number of edges joining every pair of vertices. A simple graph will mean a graph without parallel edges. The chromatic index $\chi ^ { \prime } ( G )$ is the least number of colours needed to colour the edges of $G$ in such a way that no two adjacent edges are assigned the same colour (cf. also [[Graph colouring|Graph colouring]]). If $\Delta ( G )$ is the maximum degree of $G$, then, obviously, $\Delta ( G ) \leq \chi ^ { \prime } ( G )$. The origins of chromatic graph theory may be traced back to 1852, with the birth of the [[Four-colour problem|four-colour problem]]. The first paper on edge colourings appeared 1880, when P.G. Tait [[#References|[a18]]] made the important observation that the four-colour conjecture is equivalent to the statement that every $3$-[[Regular graph|regular]] planar graph has chromatic index $3$. But after this, little was done. In 1916, D. König [[#References|[a13]]] proved that if $G$ is a bipartite graph (cf. also [[Graph, bipartite|Graph, bipartite]]), then $\chi ^ { \prime } ( G ) = \Delta ( G )$. The first non-trivial upper bound has been obtained by C.E. Shannon [[#References|[a17]]] in 1949, when he proved $\chi ^ { \prime } ( G ) \leq 3 \Delta ( G ) / 2$ for an arbitrary graph $G$. The great breakthrough occurred in 1964, however, when V.G. Vizing [[#References|[a19]]] gave the following surprisingly strong result, now known as Vizing's theorem: If $G$ is a graph, then
  
The cornerstone of Vizing's proof is a brilliant recolouring technique. Up to now (1999) all further proofs of his theorem are based more or less on this method (see, for example, [[#References|[a5]]], [[#References|[a10]]], and [[#References|[a22]]]). In addition, the proof of Vizing's theorem can be used to obtain a polynomial-time algorithm to colour the edges of every graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004018.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004019.png" /> colours. Nowadays, graphs are normally divided into two classes: those with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004020.png" /> are called class-1 graphs, and the others class-2 graphs. Class-2 graphs are relatively scarce, even among the simple graphs [[#References|[a9]]]. In view of König's result, bipartite graphs are of class 1; however, the general question whether a given graph is class 1 or class 2 is very difficult, and it is known as the classification problem. This problem is extremely important and has received wide interest. The difficulty of the classification problem lies in the fact that it is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004021.png" />-complete (cf. [[#References|[a12]]]; [[Complexity theory|Complexity theory]]), and that its solution would imply the four-colour theorem. Very little progress has been made for general graphs, and hence it is natural to consider this problem for special families. For regular graphs the so-called one-factorization conjecture goes back to the 1950s: Every simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004022.png" />-regular graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004023.png" /> vertices is class 1 (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004024.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004025.png" />-factorizable) when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004026.png" />. This conjecture is still open (1999). The best partial solutions go back to A.G. Chetwynd and A.J.W. Hilton [[#References|[a7]]] and T. Niessen and L. Volkmann [[#References|[a15]]]. They showed independently that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004027.png" />-factorization conjecture is valid if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004028.png" />. Appreciable progress has also been achieved in the particular case of planar graphs. On the one hand, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004029.png" />, then a planar graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004030.png" /> can lie in either class 1 or class 2. On the other hand, Vizing [[#References|[a20]]] has proved that every simple planar graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004031.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004032.png" /> is necessarily of class 1. However, the problem of determining what happens when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004033.png" /> is either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004034.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004035.png" /> remains open, and has led [[#References|[a20]]] to the planar graph conjecture: Every simple planar graph of maximum degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004036.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004037.png" /> is of class 1.
+
\begin{equation*} \Delta ( G ) \leq \chi ^ { \prime } ( G ) \leq \Delta ( G ) + \mu ( G ). \end{equation*}
  
The total chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004038.png" /> is the least number of colours needed to colour the elements (edges and vertices) of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004039.png" /> so that adjacent elements are coloured differently. The centre of interest lies in the still (1999) unproven total colouring conjecture of Vizing [[#References|[a20]]] and M. Behzad [[#References|[a3]]] that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004040.png" /> for a simple graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004041.png" />. A.J.W. Hilton and H.R. Hind [[#References|[a11]]] proved this conjecture by vertex colouring methods when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004042.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004043.png" /> is the number of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004044.png" />. Also, Vizing's theorem is a powerful tool in attacking this conjecture. For example, K.H. Chew [[#References|[a6]]] has given a new proof of the Hilton–Hind result by transforming the total colouring problem to an edge-colouring problem. Using probabilistic methods, recently M. Molloy and B. Reed [[#References|[a2]]] have obtained the following very deep theorem: There is an absolute constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004045.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004046.png" /> for every simple graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004047.png" />. See [[#References|[a23]]] for a thorough treatment of this topic.
+
In particular, $\Delta ( G ) \leq \chi ^ { \prime } ( G ) \leq \Delta ( G ) + 1$ if $G$ is simple.
  
In order to give reasonable upper bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004048.png" />, Vizing [[#References|[a21]]] introduced the concept of list colouring: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004049.png" /> is the list-chromatic index of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004050.png" />, then, obviously, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004051.png" />. Vizing [[#References|[a21]]] even posed the still open (1999) list colouring conjecture: Every graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004052.png" /> satisfies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004053.png" />. With a surprisingly short proof, F. Galvin [[#References|[a1]]] showed that the list colouring conjecture is true for bipartite graphs. A.V. Kostochka [[#References|[a14]]] proved that if all cycles in a simple graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004054.png" /> are sufficiently long relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004055.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004056.png" />. If the list colouring conjecture is true, then, according to Vizing's theorem, the same bound would hold for any simple graph.
+
The cornerstone of Vizing's proof is a brilliant recolouring technique. Up to now (1999) all further proofs of his theorem are based more or less on this method (see, for example, [[#References|[a5]]], [[#References|[a10]]], and [[#References|[a22]]]). In addition, the proof of Vizing's theorem can be used to obtain a polynomial-time algorithm to colour the edges of every graph $G$ with $\Delta ( G ) + \mu ( G )$ colours. Nowadays, graphs are normally divided into two classes: those with $\chi ^ { \prime } ( G ) = \Delta ( G )$ are called class-1 graphs, and the others class-2 graphs. Class-2 graphs are relatively scarce, even among the simple graphs [[#References|[a9]]]. In view of König's result, bipartite graphs are of class 1; however, the general question whether a given graph is class 1 or class 2 is very difficult, and it is known as the classification problem. This problem is extremely important and has received wide interest. The difficulty of the classification problem lies in the fact that it is $\cal N P$-complete (cf. [[#References|[a12]]]; [[Complexity theory|Complexity theory]]), and that its solution would imply the four-colour theorem. Very little progress has been made for general graphs, and hence it is natural to consider this problem for special families. For regular graphs the so-called one-factorization conjecture goes back to the 1950s: Every simple $r$-regular graph with $2 n$ vertices is class 1 (i.e. $G$ is $1$-factorizable) when $r \geq n$. This conjecture is still open (1999). The best partial solutions go back to A.G. Chetwynd and A.J.W. Hilton [[#References|[a7]]] and T. Niessen and L. Volkmann [[#References|[a15]]]. They showed independently that the $1$-factorization conjecture is valid if $r \geq ( \sqrt { 7 } - 1 ) n \approx 1.647 n$. Appreciable progress has also been achieved in the particular case of planar graphs. On the one hand, if $\Delta ( G ) \leq 5$, then a planar graph $G$ can lie in either class 1 or class 2. On the other hand, Vizing [[#References|[a20]]] has proved that every simple planar graph $G$ with $\Delta ( G ) \geq 8$ is necessarily of class 1. However, the problem of determining what happens when $\Delta ( G )$ is either $6$ or $7$ remains open, and has led [[#References|[a20]]] to the planar graph conjecture: Every simple planar graph of maximum degree $6$ or $7$ is of class 1.
  
The determination of the chromatic index can be transformed into a problem dealing with the chromatic number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004057.png" />. Namely, from the definition it is immediate that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004058.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004059.png" /> is the line graph of the simple graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004060.png" />. If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004061.png" /> is the clique number (cf. also [[Fixed-point property|Fixed-point property]]) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004062.png" />, then Vizing's theorem implies
+
The total chromatic number $\chi _ { T } ( G )$ is the least number of colours needed to colour the elements (edges and vertices) of a graph $G$ so that adjacent elements are coloured differently. The centre of interest lies in the still (1999) unproven total colouring conjecture of Vizing [[#References|[a20]]] and M. Behzad [[#References|[a3]]] that $\chi _ { T } ( G ) \leq \Delta ( G ) + 2$ for a simple graph $G$. A.J.W. Hilton and H.R. Hind [[#References|[a11]]] proved this conjecture by vertex colouring methods when $\Delta ( G ) \geq 3 n / 4$, where $n$ is the number of vertices of $G$. Also, Vizing's theorem is a powerful tool in attacking this conjecture. For example, K.H. Chew [[#References|[a6]]] has given a new proof of the Hilton–Hind result by transforming the total colouring problem to an edge-colouring problem. Using probabilistic methods, recently M. Molloy and B. Reed [[#References|[a2]]] have obtained the following very deep theorem: There is an absolute constant $C$ such that $\chi _ { T } ( G ) \leq \Delta ( G ) + C$ for every simple graph $G$. See [[#References|[a23]]] for a thorough treatment of this topic.
  
<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/v/v120/v120040/v12004063.png" /></td> </tr></table>
+
In order to give reasonable upper bounds for $\chi _ { T } ( G )$, Vizing [[#References|[a21]]] introduced the concept of list colouring: If $\chi _ { l } ^ { \prime } ( G )$ is the list-chromatic index of a graph $G$, then, obviously, $\chi ^ { \prime } ( G ) \leq \chi _ { l } ^ { \prime } ( G )$. Vizing [[#References|[a21]]] even posed the still open (1999) list colouring conjecture: Every graph $G$ satisfies $\chi ^ { \prime } ( G ) = \chi _ { l } ^ { \prime } ( G )$. With a surprisingly short proof, F. Galvin [[#References|[a1]]] showed that the list colouring conjecture is true for bipartite graphs. A.V. Kostochka [[#References|[a14]]] proved that if all cycles in a simple graph $G$ are sufficiently long relative to $\Delta ( G )$, then $\chi _ { l } ^ { \prime } ( G ) \leq \Delta ( G ) + 1$. If the list colouring conjecture is true, then, according to Vizing's theorem, the same bound would hold for any simple graph.
  
Therefore, this bound is called [[#References|[a16]]] the Vizing bound. L.W. Beineke [[#References|[a4]]] characterized line graphs by nine forbidden induced subgraphs. Using only four forbidden induced subgraphs of Beineke's nine graphs, S.A. Choudom [[#References|[a8]]] determined two superclasses of line graphs for which the Vizing bound is also valid. Thus, since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004064.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004065.png" /> is not a triangle, Choudom's result extends Vizing's theorem. The most general contribution in this area was found by H. Randerath [[#References|[a16]]]: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004066.png" /> is a simple graph containing neither a complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004067.png" />-graph with an edge missing nor a claw <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004068.png" /> with one subdivided edge as an induced subgraph, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004069.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004070.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004071.png" />.
+
The determination of the chromatic index can be transformed into a problem dealing with the chromatic number $\chi ( G )$. Namely, from the definition it is immediate that $\chi ^ { \prime } ( G ) = \chi ( L ( G ) )$, where $L ( G )$ is the [[line graph]] of the simple graph $G$. If, in addition, $\omega ( G )$ is the clique number (cf. also [[Fixed-point property|Fixed-point property]]) of $G$, then Vizing's theorem implies
 +
 
 +
\begin{equation*} \chi ( L ( G ) ) \leq \omega ( L ( G ) ) + 1. \end{equation*}
 +
 
 +
Therefore, this bound is called [[#References|[a16]]] the Vizing bound. L.W. Beineke [[#References|[a4]]] characterized line graphs by nine forbidden [[induced subgraph]]s. Using only four forbidden induced subgraphs of Beineke's nine graphs, S.A. Choudom [[#References|[a8]]] determined two superclasses of line graphs for which the Vizing bound is also valid. Thus, since $\Delta ( G ) = \omega ( L ( G ) )$ if $G$ is not a triangle, Choudom's result extends Vizing's theorem. The most general contribution in this area was found by H. Randerath [[#References|[a16]]]: If $G$ is a simple graph containing neither a complete $5$-graph with an edge missing nor a claw $K _ { 1,3 }$ with one subdivided edge as an induced subgraph, then $\chi ( G )$ is equal to $\omega ( G )$ or $\omega ( G ) + 1$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F. Galvin,  "The list chromatic index of a bipartite multigraph"  ''J. Combin. Th. B'' , '''68'''  (1995)  pp. 153–158</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Molloy,  B. Reed,  "A bound on the total chromatic number"  ''Combinatorica'' , '''18'''  (1998)  pp. 241–280</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Behzad,  "Graphs and their chromatic numbers"  ''Doctoral Thesis Michigan State Univ.''  (1965)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L.W. Beineke,  "Derived graphs and digraphs" , ''Beiträge zur Graphentheorie'' , Teubner  (1968)  pp. 17–33</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  K.H. Chew,  "On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs"  ''Discrete Math.'' , '''171'''  (1997)  pp. 283–286</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  K.H. Chew,  "Total chromatic number of graphs of high maximum degree"  ''J. Combin. Math. Combin. Comput.'' , '''18'''  (1995)  pp. 245–254</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.G. Chetwynd,  A.J.W. Hilton,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004072.png" />-factorizing regular graphs of high degree: an improved bound"  ''Discrete Math.'' , '''75'''  (1989)  pp. 103–112</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  S.A. Choudom,  "Chromatic bound for a class of graphs"  ''Quart. J. Math.'' , '''28'''  (1977)  pp. 257–270</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  P. Erdös,  R.J. Wilson,  "On the chromatic index of almost all graphs"  ''J. Combin. Th.'' , '''23 B'''  (1977)  pp. 255–257</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  M.K. Goldberg,  "Edge-coloring of multigraphs: recoloring technique"  ''J. Graph Theory'' , '''8'''  (1984)  pp. 123–137</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  A.J.W. Hilton,  H.R. Hind,  "The total chromatic number of graphs having large maximum degree"  ''Discrete Math.'' , '''117'''  (1993)  pp. 127–140</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  I. Holyer,  "The NP-completeness of edge-coloring"  ''SIAM J. Comput.'' , '''10'''  (1981)  pp. 718–720</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  D. König,  "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre"  ''Math. Ann.'' , '''77'''  (1916)  pp. 453–465</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  A.V. Kostochka,  "List edge chromatic number of graphs with large girth"  ''Discrete Math.'' , '''101'''  (1992)  pp. 189–201</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  T. Niessen,  L. Volkmann,  "Class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004073.png" /> conditions depending on the minimum degree and the number of vertices of maximum degree"  ''J. Graph Theory'' , '''14'''  (1990)  pp. 225–246</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  H. Randerath,  "The Vizing bound for the chromatic number based on forbidden pairs"  ''Doctoral Thesis RWTH Aachen''  (1998)</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  C.E. Shannon,  "A theorem on coloring the lines of a network"  ''J. Math. Phys.'' , '''28'''  (1949)  pp. 148–151</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  P.G. Tait,  "On the colouring of maps"  ''Proc. R. Soc. Edinburgh'' , '''10'''  (1880)  pp. 501–503; 729</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  V.G. Vizing,  "On an estimate of the chromatic class of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v120/v120040/v12004074.png" />-graph"  ''Diskret. Anal.'' , '''3'''  (1964)  pp. 25–30  (In Russian)</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  V.G. Vizing,  "Critical graphs with a given chromatic class"  ''Diskret. Anal.'' , '''5'''  (1965)  pp. 9–17  (In Russian)</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  V.G. Vizing,  "Vertex colouring with given colours"  ''Diskret. Anal.'' , '''29'''  (1976)  pp. 3–10  (In Russian)</TD></TR><TR><TD valign="top">[a22]</TD> <TD valign="top">  L. Volkmann,  "Fundamente der Graphentheorie" , Springer  (1996)</TD></TR><TR><TD valign="top">[a23]</TD> <TD valign="top">  H.P. Yap,  "Total colourings of graphs" , ''Lecture Notes Math.'' , '''1623''' , Springer  (1996)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  F. Galvin,  "The list chromatic index of a bipartite multigraph"  ''J. Combin. Th. B'' , '''68'''  (1995)  pp. 153–158</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  M. Molloy,  B. Reed,  "A bound on the total chromatic number"  ''Combinatorica'' , '''18'''  (1998)  pp. 241–280</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  M. Behzad,  "Graphs and their chromatic numbers"  ''Doctoral Thesis Michigan State Univ.''  (1965)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  L.W. Beineke,  "Derived graphs and digraphs" , ''Beiträge zur Graphentheorie'' , Teubner  (1968)  pp. 17–33</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  K.H. Chew,  "On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs"  ''Discrete Math.'' , '''171'''  (1997)  pp. 283–286</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  K.H. Chew,  "Total chromatic number of graphs of high maximum degree"  ''J. Combin. Math. Combin. Comput.'' , '''18'''  (1995)  pp. 245–254</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  A.G. Chetwynd,  A.J.W. Hilton,  "$1$-factorizing regular graphs of high degree: an improved bound"  ''Discrete Math.'' , '''75'''  (1989)  pp. 103–112</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  S.A. Choudom,  "Chromatic bound for a class of graphs"  ''Quart. J. Math.'' , '''28'''  (1977)  pp. 257–270</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  P. Erdös,  R.J. Wilson,  "On the chromatic index of almost all graphs"  ''J. Combin. Th.'' , '''23 B'''  (1977)  pp. 255–257</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  M.K. Goldberg,  "Edge-coloring of multigraphs: recoloring technique"  ''J. Graph Theory'' , '''8'''  (1984)  pp. 123–137</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  A.J.W. Hilton,  H.R. Hind,  "The total chromatic number of graphs having large maximum degree"  ''Discrete Math.'' , '''117'''  (1993)  pp. 127–140</td></tr><tr><td valign="top">[a12]</td> <td valign="top">  I. Holyer,  "The NP-completeness of edge-coloring"  ''SIAM J. Comput.'' , '''10'''  (1981)  pp. 718–720</td></tr><tr><td valign="top">[a13]</td> <td valign="top">  D. König,  "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre"  ''Math. Ann.'' , '''77'''  (1916)  pp. 453–465</td></tr><tr><td valign="top">[a14]</td> <td valign="top">  A.V. Kostochka,  "List edge chromatic number of graphs with large girth"  ''Discrete Math.'' , '''101'''  (1992)  pp. 189–201</td></tr><tr><td valign="top">[a15]</td> <td valign="top">  T. Niessen,  L. Volkmann,  "Class $1$ conditions depending on the minimum degree and the number of vertices of maximum degree"  ''J. Graph Theory'' , '''14'''  (1990)  pp. 225–246</td></tr><tr><td valign="top">[a16]</td> <td valign="top">  H. Randerath,  "The Vizing bound for the chromatic number based on forbidden pairs"  ''Doctoral Thesis RWTH Aachen''  (1998)</td></tr><tr><td valign="top">[a17]</td> <td valign="top">  C.E. Shannon,  "A theorem on coloring the lines of a network"  ''J. Math. Phys.'' , '''28'''  (1949)  pp. 148–151</td></tr><tr><td valign="top">[a18]</td> <td valign="top">  P.G. Tait,  "On the colouring of maps"  ''Proc. R. Soc. Edinburgh'' , '''10'''  (1880)  pp. 501–503; 729</td></tr><tr><td valign="top">[a19]</td> <td valign="top">  V.G. Vizing,  "On an estimate of the chromatic class of a $p$-graph"  ''Diskret. Anal.'' , '''3'''  (1964)  pp. 25–30  (In Russian)</td></tr><tr><td valign="top">[a20]</td> <td valign="top">  V.G. Vizing,  "Critical graphs with a given chromatic class"  ''Diskret. Anal.'' , '''5'''  (1965)  pp. 9–17  (In Russian)</td></tr><tr><td valign="top">[a21]</td> <td valign="top">  V.G. Vizing,  "Vertex colouring with given colours"  ''Diskret. Anal.'' , '''29'''  (1976)  pp. 3–10  (In Russian)</td></tr><tr><td valign="top">[a22]</td> <td valign="top">  L. Volkmann,  "Fundamente der Graphentheorie" , Springer  (1996)</td></tr><tr><td valign="top">[a23]</td> <td valign="top">  H.P. Yap,  "Total colourings of graphs" , ''Lecture Notes Math.'' , '''1623''' , Springer  (1996)</td></tr></table>

Latest revision as of 09:33, 19 January 2021

Let $G$ be a graph (assumed to be finite, undirected and loop-less), and let $\mu ( G )$ be the maximum number of edges joining every pair of vertices. A simple graph will mean a graph without parallel edges. The chromatic index $\chi ^ { \prime } ( G )$ is the least number of colours needed to colour the edges of $G$ in such a way that no two adjacent edges are assigned the same colour (cf. also Graph colouring). If $\Delta ( G )$ is the maximum degree of $G$, then, obviously, $\Delta ( G ) \leq \chi ^ { \prime } ( G )$. The origins of chromatic graph theory may be traced back to 1852, with the birth of the four-colour problem. The first paper on edge colourings appeared 1880, when P.G. Tait [a18] made the important observation that the four-colour conjecture is equivalent to the statement that every $3$-regular planar graph has chromatic index $3$. But after this, little was done. In 1916, D. König [a13] proved that if $G$ is a bipartite graph (cf. also Graph, bipartite), then $\chi ^ { \prime } ( G ) = \Delta ( G )$. The first non-trivial upper bound has been obtained by C.E. Shannon [a17] in 1949, when he proved $\chi ^ { \prime } ( G ) \leq 3 \Delta ( G ) / 2$ for an arbitrary graph $G$. The great breakthrough occurred in 1964, however, when V.G. Vizing [a19] gave the following surprisingly strong result, now known as Vizing's theorem: If $G$ is a graph, then

\begin{equation*} \Delta ( G ) \leq \chi ^ { \prime } ( G ) \leq \Delta ( G ) + \mu ( G ). \end{equation*}

In particular, $\Delta ( G ) \leq \chi ^ { \prime } ( G ) \leq \Delta ( G ) + 1$ if $G$ is simple.

The cornerstone of Vizing's proof is a brilliant recolouring technique. Up to now (1999) all further proofs of his theorem are based more or less on this method (see, for example, [a5], [a10], and [a22]). In addition, the proof of Vizing's theorem can be used to obtain a polynomial-time algorithm to colour the edges of every graph $G$ with $\Delta ( G ) + \mu ( G )$ colours. Nowadays, graphs are normally divided into two classes: those with $\chi ^ { \prime } ( G ) = \Delta ( G )$ are called class-1 graphs, and the others class-2 graphs. Class-2 graphs are relatively scarce, even among the simple graphs [a9]. In view of König's result, bipartite graphs are of class 1; however, the general question whether a given graph is class 1 or class 2 is very difficult, and it is known as the classification problem. This problem is extremely important and has received wide interest. The difficulty of the classification problem lies in the fact that it is $\cal N P$-complete (cf. [a12]; Complexity theory), and that its solution would imply the four-colour theorem. Very little progress has been made for general graphs, and hence it is natural to consider this problem for special families. For regular graphs the so-called one-factorization conjecture goes back to the 1950s: Every simple $r$-regular graph with $2 n$ vertices is class 1 (i.e. $G$ is $1$-factorizable) when $r \geq n$. This conjecture is still open (1999). The best partial solutions go back to A.G. Chetwynd and A.J.W. Hilton [a7] and T. Niessen and L. Volkmann [a15]. They showed independently that the $1$-factorization conjecture is valid if $r \geq ( \sqrt { 7 } - 1 ) n \approx 1.647 n$. Appreciable progress has also been achieved in the particular case of planar graphs. On the one hand, if $\Delta ( G ) \leq 5$, then a planar graph $G$ can lie in either class 1 or class 2. On the other hand, Vizing [a20] has proved that every simple planar graph $G$ with $\Delta ( G ) \geq 8$ is necessarily of class 1. However, the problem of determining what happens when $\Delta ( G )$ is either $6$ or $7$ remains open, and has led [a20] to the planar graph conjecture: Every simple planar graph of maximum degree $6$ or $7$ is of class 1.

The total chromatic number $\chi _ { T } ( G )$ is the least number of colours needed to colour the elements (edges and vertices) of a graph $G$ so that adjacent elements are coloured differently. The centre of interest lies in the still (1999) unproven total colouring conjecture of Vizing [a20] and M. Behzad [a3] that $\chi _ { T } ( G ) \leq \Delta ( G ) + 2$ for a simple graph $G$. A.J.W. Hilton and H.R. Hind [a11] proved this conjecture by vertex colouring methods when $\Delta ( G ) \geq 3 n / 4$, where $n$ is the number of vertices of $G$. Also, Vizing's theorem is a powerful tool in attacking this conjecture. For example, K.H. Chew [a6] has given a new proof of the Hilton–Hind result by transforming the total colouring problem to an edge-colouring problem. Using probabilistic methods, recently M. Molloy and B. Reed [a2] have obtained the following very deep theorem: There is an absolute constant $C$ such that $\chi _ { T } ( G ) \leq \Delta ( G ) + C$ for every simple graph $G$. See [a23] for a thorough treatment of this topic.

In order to give reasonable upper bounds for $\chi _ { T } ( G )$, Vizing [a21] introduced the concept of list colouring: If $\chi _ { l } ^ { \prime } ( G )$ is the list-chromatic index of a graph $G$, then, obviously, $\chi ^ { \prime } ( G ) \leq \chi _ { l } ^ { \prime } ( G )$. Vizing [a21] even posed the still open (1999) list colouring conjecture: Every graph $G$ satisfies $\chi ^ { \prime } ( G ) = \chi _ { l } ^ { \prime } ( G )$. With a surprisingly short proof, F. Galvin [a1] showed that the list colouring conjecture is true for bipartite graphs. A.V. Kostochka [a14] proved that if all cycles in a simple graph $G$ are sufficiently long relative to $\Delta ( G )$, then $\chi _ { l } ^ { \prime } ( G ) \leq \Delta ( G ) + 1$. If the list colouring conjecture is true, then, according to Vizing's theorem, the same bound would hold for any simple graph.

The determination of the chromatic index can be transformed into a problem dealing with the chromatic number $\chi ( G )$. Namely, from the definition it is immediate that $\chi ^ { \prime } ( G ) = \chi ( L ( G ) )$, where $L ( G )$ is the line graph of the simple graph $G$. If, in addition, $\omega ( G )$ is the clique number (cf. also Fixed-point property) of $G$, then Vizing's theorem implies

\begin{equation*} \chi ( L ( G ) ) \leq \omega ( L ( G ) ) + 1. \end{equation*}

Therefore, this bound is called [a16] the Vizing bound. L.W. Beineke [a4] characterized line graphs by nine forbidden induced subgraphs. Using only four forbidden induced subgraphs of Beineke's nine graphs, S.A. Choudom [a8] determined two superclasses of line graphs for which the Vizing bound is also valid. Thus, since $\Delta ( G ) = \omega ( L ( G ) )$ if $G$ is not a triangle, Choudom's result extends Vizing's theorem. The most general contribution in this area was found by H. Randerath [a16]: If $G$ is a simple graph containing neither a complete $5$-graph with an edge missing nor a claw $K _ { 1,3 }$ with one subdivided edge as an induced subgraph, then $\chi ( G )$ is equal to $\omega ( G )$ or $\omega ( G ) + 1$.

References

[a1] F. Galvin, "The list chromatic index of a bipartite multigraph" J. Combin. Th. B , 68 (1995) pp. 153–158
[a2] M. Molloy, B. Reed, "A bound on the total chromatic number" Combinatorica , 18 (1998) pp. 241–280
[a3] M. Behzad, "Graphs and their chromatic numbers" Doctoral Thesis Michigan State Univ. (1965)
[a4] L.W. Beineke, "Derived graphs and digraphs" , Beiträge zur Graphentheorie , Teubner (1968) pp. 17–33
[a5] K.H. Chew, "On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs" Discrete Math. , 171 (1997) pp. 283–286
[a6] K.H. Chew, "Total chromatic number of graphs of high maximum degree" J. Combin. Math. Combin. Comput. , 18 (1995) pp. 245–254
[a7] A.G. Chetwynd, A.J.W. Hilton, "$1$-factorizing regular graphs of high degree: an improved bound" Discrete Math. , 75 (1989) pp. 103–112
[a8] S.A. Choudom, "Chromatic bound for a class of graphs" Quart. J. Math. , 28 (1977) pp. 257–270
[a9] P. Erdös, R.J. Wilson, "On the chromatic index of almost all graphs" J. Combin. Th. , 23 B (1977) pp. 255–257
[a10] M.K. Goldberg, "Edge-coloring of multigraphs: recoloring technique" J. Graph Theory , 8 (1984) pp. 123–137
[a11] A.J.W. Hilton, H.R. Hind, "The total chromatic number of graphs having large maximum degree" Discrete Math. , 117 (1993) pp. 127–140
[a12] I. Holyer, "The NP-completeness of edge-coloring" SIAM J. Comput. , 10 (1981) pp. 718–720
[a13] D. König, "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" Math. Ann. , 77 (1916) pp. 453–465
[a14] A.V. Kostochka, "List edge chromatic number of graphs with large girth" Discrete Math. , 101 (1992) pp. 189–201
[a15] T. Niessen, L. Volkmann, "Class $1$ conditions depending on the minimum degree and the number of vertices of maximum degree" J. Graph Theory , 14 (1990) pp. 225–246
[a16] H. Randerath, "The Vizing bound for the chromatic number based on forbidden pairs" Doctoral Thesis RWTH Aachen (1998)
[a17] C.E. Shannon, "A theorem on coloring the lines of a network" J. Math. Phys. , 28 (1949) pp. 148–151
[a18] P.G. Tait, "On the colouring of maps" Proc. R. Soc. Edinburgh , 10 (1880) pp. 501–503; 729
[a19] V.G. Vizing, "On an estimate of the chromatic class of a $p$-graph" Diskret. Anal. , 3 (1964) pp. 25–30 (In Russian)
[a20] V.G. Vizing, "Critical graphs with a given chromatic class" Diskret. Anal. , 5 (1965) pp. 9–17 (In Russian)
[a21] V.G. Vizing, "Vertex colouring with given colours" Diskret. Anal. , 29 (1976) pp. 3–10 (In Russian)
[a22] L. Volkmann, "Fundamente der Graphentheorie" , Springer (1996)
[a23] H.P. Yap, "Total colourings of graphs" , Lecture Notes Math. , 1623 , Springer (1996)
How to Cite This Entry:
Vizing theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Vizing_theorem&oldid=17012
This article was adapted from an original article by Lutz Volkmann (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article