View source for Vizing theorem

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

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

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.

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.

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

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

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 <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" />.

====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>