Vizing theorem

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)