Graph Edge Coloring: A Survey

Abstract

Graph edge coloring has a rich theory, many applications and beautiful conjectures, and it is studied not only by mathematicians, but also by computer scientists. In this survey, written for the non-expert, we shall describe some main results and techniques and state some of the many popular conjectures in the theory. Besides known results a new basic result about brooms is obtained.

1 Preliminaries and Conjectures

Graph edge coloring is a well established subject in the field of graph theory, it is one of the basic combinatorial optimization problems: color the edges of a graphG with as few colors as possible such that each edge receives a color and adjacent edges, that is, different edges incident to a common vertex, receive different colors. The minimum number of colors needed for such a coloring of G is called the chromatic index of G, written $\chi '(G)$. By a result of Holyer [58], the determination of the chromatic index is an NP-hard optimization problem. The NP-hardness gives rise to the necessity of using heuristic algorithms. In particular, we are interested in upper bounds for the chromatic index that can be efficiently realized by a coloring algorithm. A graph parameter $\rho$ is called an efficiently realizable upper bound for $\chi '$ if there exists an polynomial-time algorithm that colors, for every graph G, the edges of G using at most $\rho (G)$ colors. It follows from a result by Shannon [105] that $\tfrac{3}{2}\chi '$ is an efficiently realizable upper bound for $\chi '$. Motivated by a conjecture proposed, independently, by Goldberg, Andersen, Gupta, and Seymour (see Sect. 1.2), Hochbaum et al. [57] made the following suggestion:

Conjecture 1

(Hochbaum, Nishizeki, and Shmoys) $\chi '+1$ is an efficiently realizable upper bound for $\chi '$.

Provided that $\mathsf{P}\not =\mathsf{NP}$, $\chi '+1$ would be the best possible efficiently realizable upper bound for the chromatic index, so the above conjecture suggests the best possible approximation result for the chromatic index. The approximation problem for the chromatic index has received a lot of attention and we shall discuss recent developments in this paper. Another important type of edge coloring problems considered in this paper deals with the chromatic index of graphs belonging to a specific graph property, that is, to a class of graphs closed under isomorphisms.

There are two monographs devoted to graph edge coloring. The first monograph by Fiorini and Wilson [41] appeared in 1977 and deals mainly with edge coloring of simple graphs. The second monograph by Stiebitz et al.  [108] was published in 2012 and gives much more attention to edge coloring of graphs having multiple edges and, in particular, to the new method invented by Tashkinov [110]. We also recommend the reader to consult the survey paper about edge coloring by McDonald [77] from 2015.

The rest of this paper is organized as follows. The reader is supported by a brief summary of the basic notation of edge coloring in Sect. 1.1. In the following sections we deal with several popular conjectures related to edge colorings. In Sect. 2 we survey the basic recoloring techniques developed by Vizing, Kierstead and Tashkinov. In Sect. 3 we prove a new adjacency lemma and show how adjacency lemmas can be used to attack Vizings’ average degree conjecture.

1.1 Basic Notation

We will mainly use the notation from the book [108]. Graphs in this paper are finite, undirected, and without loops, but may have multiple edges. The vertex set and the edge set of a graph G are denoted by V(G) and E(G), respectively. For any two sets $X, Y\subseteq V(G)$, denote by $E_G(X, Y)$ the set of edges of G joining a vertex of X and a vertex of Y, and denote by $\partial _G(X) = E_G(X, V(G){\setminus }X)$ the boundary edge set of X, that is, the set of edges with exactly one end in X. For $u,v\in V(G)$, let $E_G(u, v) = E_G(\{u\}, \{v\})$ and $E_G(v) = \partial _G(\{v\})$. Then $d_G(v)=|E_G(v)|$ is the degree of v in G, and $\mu _G(u,v)=|E_G(u,v) |$ is the multiplicity of the vertex pair u, v (where we assume that $u\not =v$). Then $\varDelta (G)=\max _{v\in V(G)}d_G(v)$ is the maximum degree of G, and $\delta (G)=\min _{v\in V(G)}d_G(v)$ is the minimum degree of G. Furthermore, $\mu (G)=\max _{u\not =v}\mu _G(u,v)$ is the maximum multiplicity of G, and a graph G with $\mu (G)\le 1$ is called a simple graph. If H is a subgraph of G, we write $H\subseteq G$. With G[X] we denote the subgraph of Ginduced by the subset X of V(G), that is, $V(G[X])=X$ and $E(G[X])=E_G(X,X)$. A subgraph H of G is an induced subgraph of G if $H=G[V(H)]$. For an edge $e\in E(G)$, $G-e$ denotes the subgraph of G obtained from G by deleting the edge e; and for $F\subseteq E(G)$ let $G-F=(V(G),E(G){\setminus }F)$.

A (proper) k-edge-coloring of a graph G is a mapping $\varphi$ from E(G) to $\{1, 2, \ldots , k\}$ (whose elements are called colors) such that no two adjacent edges receive the same color, that is, $\varphi (e)\not =\varphi (e')$ whenever $e, e'\in E_G(v)$ for some vertex $v\in V(G)$ and $e\not =e'$. The set of all k-edge-colorings of a graph G is denoted by ${\mathcal {C}^k}(G)$. Then the chromatic index $\chi '(G)$ is the least integer k such that ${\mathcal {C}^k}(G)\not =\emptyset$. For a coloring $\varphi \in {\mathcal {C}^k}(G)$ and a color $\alpha \in \{1, 2, \ldots , k\}$, the edge set

$$\begin{aligned} E_{\varphi ,\alpha }=\left\{ e\in E(G) \;|\; \varphi (e)=\alpha \right\} \end{aligned}$$

is called a color class. Then every vertex v of G is incident with at most one edge of $E_{\varphi ,\alpha }$, i.e., $E_{\varphi ,\alpha }$ is a matching of G (possibly empty). So, there is a one-to-one correspondence between k-edge-colorings of G and partitions $(E_1,E_2, \ldots , E_k)$ of E(G) into k matchings (color classes); and the chromatic index of G is the minimum number of matchings into which the edge set of G can be partitioned.

A simple, but very useful recoloring technique for the edge color problem was developed by König [67], Shannon [105], and Vizing [114, 116]. Let G be a graph, let $F\subseteq E(G)$ be an edge set, and let $\varphi \in {\mathcal {C}^k}(G-F)$ be a coloring for some integer $k\ge 0$; $\varphi$ is then called a partialk-edge-coloring of G. For a vertex $v \in V(G)$, define the two color sets

$$\begin{aligned} \varphi (v)=\left\{ \varphi (e) \;|\; e \in E_G(v) {\setminus }F \right\} \; \mathrm{and} \; \overline{\varphi }(v)=\{1, 2, \ldots , k \}{\setminus }\varphi (v). \end{aligned}$$

We call $\varphi (v)$ the set of colors present at v and $\overline{\varphi }(v)$ the set of colors missing at v. Evidently, we have

$$\begin{aligned} |\overline{\varphi }(v)|=k-d_G(v)+|E_G(v) \cap F|. \end{aligned}$$

(1.1)

To obtain a new coloring of $G-F$, choose two distinct colors $\alpha , \beta$ and consider the subgraph H of G with $V(H)=V(G)$ and $E(H)=E_{\varphi ,\alpha } \cup E_{\varphi ,\beta }$. Then every component of H is either a path or an even cycle whose edges are colored alternately by $\alpha$ and $\beta$, and we refer to such a component as an $(\alpha ,\beta )$-chain of G with respect to $\varphi$. Now choose an arbitrary $(\alpha ,\beta )$-chain C of G with respect to $\varphi$. If we interchange the colors $\alpha$ and $\beta$ on C, then we obtain a new k-edge-coloring $\varphi '$ of $G-F$. In what follows, we briefly say that the coloring $\varphi '$ is obtained from $\varphi$ by recoloringC, and we write $\varphi '=\varphi /C$. This operation is called a Kempe change, as a similar recoloring technique was first used by A. B. Kempe in his attempt to solve the Four-Color Problem. Furthermore, we say that an $(\alpha ,\beta )$-chain C has endsu, v if C is a path joining u and v. For a vertex v of G, we denote by $P_v(\alpha ,\beta ,\varphi )$ the unique $(\alpha ,\beta )$-chain of $G-F$ with respect to $\varphi$ that contains the vertex v. If it is clear that we refer to the coloring $\varphi$, then we also write $P_v(\alpha ,\beta )$ instead of $P_v(\alpha ,\beta ,\varphi )$. If exactly one of the two colors $\alpha$ or $\beta$ belongs to $\overline{\varphi }(v)$, then $P_v(\alpha ,\beta ,\varphi )$ is a path, where one end is v and the other end is some vertex $u\not =v$ such that $\overline{\varphi }(u)$ contains either $\alpha$ or $\beta$. For a vertex set $X \subseteq V(G)$, we define

$$\begin{aligned} \overline{\varphi }(X)=\bigcup _{v\in X}\overline{\varphi }(v). \end{aligned}$$

We also write $\overline{\varphi }(v_1,v_2,\ldots ,v_p)$ instead of $\overline{\varphi }(\{v_1, v_2, \ldots v_p\})$. The set X is called $\varphi$-elementary if $\overline{\varphi }(u) \cap \overline{\varphi }(v)=\emptyset$ for every two distinct vertices $u,v \in X$. The set X is called $\varphi$-closed if for every colored edge $f\in \partial _G(X)$ the color $\varphi (f)$ is present at every vertex of X, i.e., $\varphi (f)\in \varphi (v)$ for every $v\in X$. Finally, the set X is called strongly$\varphi$-closed if X is $\varphi$-closed and $\varphi (f) \not = \varphi (f')$ for every two colored distinct edges $f,f' \in \partial _G(X)$.

In investigating graph edge coloring problems critical graphs play an important role. This is due to the fact that problems for graphs in general may often be reduced to problems for critical graphs whose structure is more restricted. Note that $\chi '$ is a monotone graph parameter in the sense that $H\subseteq G$ implies $\chi '(H)\le \chi '(G)$. Furthermore every edge e of G satisfies

$$\begin{aligned} \chi '(G)-1\le \chi '(G-e)\le \chi '(G) \end{aligned}$$

(1.2)

A graph G is called critical if $\chi '(H)<\chi '(G)$ for every proper subgraph H of G. We call $e\in E(G)$ a critical edge of G if $\chi '(G-e)<\chi '(G)$. Clearly, if G is a critical graph, then every edge of G is critical. The converse statement is true provided that G has no isolated vertices. A graph parameter $\rho$ is called monotone if $H\subseteq G$ implies $\rho (H)\le \rho (G)$.

Lemma 1.1

(Critical Method) Let $\rho$ be a monotone graph parameter. Then the following statements hold:

• (a) Every graph G contains a critical subgraph H with $\chi '(H)=\chi '(G)$.

• (b) If every critical graph H satisfies $\chi '(H)\le \rho (H)$, then every graph G satisfies $\chi '(G)\le \rho (G)$.

Proof

Since $\chi '$ is monotone, every graph G contains a minimal subgraph H such that $\chi '(H)=\chi '(G)$. Obviously, H is critical. This proves (a). For the proof of (b), let G be any graph. By (a), there is a critical graph $H\subseteq G$ with $\chi '(H)=\chi '(G)$. Since $\rho$ is monotone, we then obtain $\chi '(G)=\chi '(H)\le \rho (H)\le \rho (G)$, as claimed. $\square$

1.2 Upper Bounds for $\chi '$ and Goldberg’s Conjecture

Since, in any edge coloring of a graph, the edges incident to a common vertex receive different colors, we obtain that $\chi '\ge \varDelta$, and in 1916 König [67] proved that equality holds for the class of bipartite graphs. That the chromatic index is bounded from above in terms of $\varDelta$, respectively in terms of $\varDelta$ and $\mu$ was proved by Shannon [105] in 1949, respectively by Vizing [114] as well as by Gupta [49] in the 1960s.

Theorem 1.1

For any graph G the following statements hold:

• (a) (Shannon) $\chi '(G) \le \frac{3}{2}\varDelta (G)$.

• (b) (Vizing and Gupta) $\chi '(G) \le \varDelta (G)+\mu (G)$.

Shannon’s proof (see [108, page 17]) yields a polynomial-time algorithm showing that $\frac{3}{2}\varDelta$ is an efficiently realizable upper bound for the chromatic index. As $\varDelta$ is a lower bound for $\chi '$, this implies that $\frac{3}{2}\chi '$ is an efficiently realizable upper bound for the chromatic index, too.

Vizing’s proof shows that $\varDelta +\mu$ is an efficiently realizable upper bound for $\chi '$ by providing a polynomial-time algorithm that colors the edges of G, step by step, without using more than $k=\varDelta (G)+\mu (G)$ colors. To extend a partial k-edge-coloring of G to the next uncolored edge $e\in E_G(u,v)$, Vizing introduced a recoloring procedure, using so called fans (see Sect. 2), in order to obtain a partial k-edge-coloring $\varphi$ such that there is a color $\alpha \in \overline{\varphi }(u) \cap \overline{\varphi }(v)$, which can then be used to color the edge e. Gupta’s proof uses a similar recoloring technique. If G is bipartite and $k=\varDelta (G)$, then, for $\varphi \in {\mathcal {C}^k}(G-e)$, there are colors $\alpha \in \overline{\varphi }(u)$ and $\beta \in \overline{\varphi }(v)$ (by (1.1) with $F=\{e\}$). Either $\alpha =\beta$ and we can color e with $\alpha$, or we recolor $P=P_v(\alpha ,\beta ,\varphi )$. As G is bipartite, G contains no odd cycle and so u does not belong to P. Consequently, for the coloring $\varphi '=\varphi /P$ we obtain $\alpha \in \overline{\varphi }(u)\cap \overline{\varphi }(v)$ and so we can color e with $\alpha$. In both cases we obtain a k-edge-coloring of G.

By the Vizing-Gupta bound, every simple graph G satisfies $\varDelta (G) \le \chi '(G) \le \varDelta (G)+1$. This leads to a natural classification of simple graphs into two classes. A graph G is said to be of class one if G is simple and $\chi '(G)=\varDelta (G)$ and of class two if G is simple and $\chi '(G)=\varDelta (G)+1$. The Classification Problem, first introduced and investigated by Vizing in a series of papers [114,115,116,117], is the problem of deciding whether a simple graph is class one or class two. On the one hand, the determination of the chromatic index is NP-hard even for the class of simple graphs (by Holyer [58]). On the other hand, the Classification Problem has lead to several beautiful conjectures, which we shall discuss in the following sections.

Note that the proof of Theorem 1.1(b) implies that Conjecture 1 holds for the class of simple graphs. To extend this result to the class of graphs having multiple edges, we need better bounds for the chromatic index. Another lower bound for the chromatic index can be obtained by using the fact that each color class in an edge coloring of a graph is a matching of that graph. Hence, given a set X of at least two vertices in a graph G, the maximum size of a color class in G[X] is $\lfloor \frac{1}{2}|X|\rfloor$, which leads to the following lower bound for the chromatic index of a graph G, provided that its order satisfies $|G|\ge 2$, namely,

$$\begin{aligned} {\scriptstyle \mathcal {W}}(G)=\max _{X\subseteq V(G), |X|\ge 2}\left\lceil \frac{|E(G[X])|}{\lfloor \frac{1}{2}|X|\rfloor }\right\rceil . \end{aligned}$$

If $|G|\le 1$, we define ${\scriptstyle \mathcal {W}}(G)=0$. The parameter ${\scriptstyle \mathcal {W}}(G)$ is called the density of G. Then every graph G satisfies $\chi '(G)\ge {\scriptstyle \mathcal {W}}(G)$, and so

$$\begin{aligned} \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)\} \le \chi '(G) \end{aligned}$$

(1.3)

It is known (see [108, page 7]) that the maximum in ${\scriptstyle \mathcal {W}}(G)$ is always attained by a vertex set whose size is odd, that is, every graph G with $|G|\ge 3$ satisfies

$$\begin{aligned} {\scriptstyle \mathcal {W}}(G)=\max _{X\subseteq V(G), |X|\ge 3 \,\text {odd}}\left\lceil \frac{2|E(G[X])|}{|X|-1}\right\rceil . \end{aligned}$$

If $G=K_{1,n}$ is a star with $n\ge 2$, then ${\scriptstyle \mathcal {W}}(G)=2$ and $\chi '(G)=\varDelta (G)=n$. This shows that there is no upper bound for $\chi '$ in terms of the density alone. On the other hand, in the 1970s the following conjecture was proposed independently by several researchers including Goldberg [44], Andersen [4], Gupta [50], Seymour [102], and possibly others. In the paper, we will refer to this conjecture as Goldberg’s conjecture.

Conjecture 2

(Goldberg’s Conjecture) Every graph G satisfies the inequality $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)+1\}$.

Goldberg’s conjecture claims that the parameter ${\tilde{\kappa }}=\max \{{\scriptstyle \mathcal {W}},\varDelta +1\}$ is an upper bound for $\chi '$. The parameter $\kappa =\max \{{\scriptstyle \mathcal {W}},\varDelta \}$ satisfies ${\tilde{\kappa }}\le \kappa +1 \le \chi '+1$ (by (1.3)). Therefore, if one can prove that ${\tilde{\kappa }}$ is an efficiently realizable upper bound for $\chi '$, then Conjecture 1 would be confirmed. In this sense Goldberg’s conjecture supports Conjecture 1. Clearly, the parameter ${\tilde{\kappa }}$ is monotone and, by Lemma 1.1, for a proof of Goldberg’s conjecture it suffices to show that every critical graph G satisfies $\chi '(G)\le {\tilde{\kappa }}(G)$.

Following Tashkinow, a graph G is called elementary if $\chi '(G)={\scriptstyle \mathcal {W}}(G)$. The significance of this equation is that the chromatic index is characterized by a min-max equality. To show that a critical graph is elementary one can use the following lemma.

Lemma 1.2

Let G be a critical graph with $\chi '(G)=k+1$ for an integer $k\ge \varDelta (G)$, let $e\in E(G)$, and let $\varphi \in {\mathcal {C}^k}(G-e)$. Then G is elementary if and only if V(G) is $\varphi$-elementary.

Proof

By the assumption, it follows that $|G|\ge 3$. First assume that G is elementary, i.e., $\chi '(G)={\scriptstyle \mathcal {W}}(G)$. Then, for every proper subgraph H of G, we obtain ${\scriptstyle \mathcal {W}}(H)\le \chi '(H)<\chi '(G)={\scriptstyle \mathcal {W}}(G)$. Therefore, the maximum in ${\scriptstyle \mathcal {W}}(G)$ is obtained by $X=V(G)$, i.e.,

$$\begin{aligned} {\scriptstyle \mathcal {W}}(G)=\left\lceil \frac{|E(G)|}{\lfloor \frac{1}{2}|G|\rfloor }\right\rceil . \end{aligned}$$

Then |G| is odd, for otherwise

$$\begin{aligned} \chi '(G)=\left\lceil \frac{2|E(G)|}{|G|}\right\rceil \le \varDelta (G), \end{aligned}$$

a contradiction. Since |G| is odd and each color class is a matching, each of the k colors is missing at at least one vertex. Suppose, on the contrary, that V(G) is not $\varphi$-elementary. Then some color is missing at at least three vertices. Using (1.1), we then obtain that

$$\begin{aligned} \sum _{v\in V(G)}(k-d_G(v))+2=\sum _{v\in V(G)}|\overline{\varphi }(v)|\ge k+2, \end{aligned}$$

which leads to $k|G|-2|E(G)|\ge k$, and so to $k(|G|-1)\ge 2|E(G)|$. Since |G| is odd, we then obtain

$$\begin{aligned} k\ge \left\lceil \frac{|E(G)|}{\lfloor \frac{1}{2}|G|\rfloor }\right\rceil ={\scriptstyle \mathcal {W}}(G)=\chi '(G)=k+1, \end{aligned}$$

a contradiction. Hence V(G) is $\varphi$-elementary.

Now assume that V(G) is $\varphi$-elementary. Again, each of the k colors is present at an even number of vertices of G. So if |G| is even, then each color is present at any vertex of G, that is, each color class is a perfect matching. Since one edge is uncolored, this leads to $|E(G)|=k(|G|/2)+1$, and hence to $k<(2|E(G)|)/|G|\le \varDelta (G)$, a contradiction. This shows that |G| is odd. Then each color is missing at exactly one vertex, and so $|E(G)|=k\frac{|G|-1}{2}+1$. This leads to

$$\begin{aligned} {\scriptstyle \mathcal {W}}(G)\ge \left\lceil \frac{|E(G)|}{\lfloor \frac{1}{2}|G|\rfloor }\right\rceil = \left\lceil k+ \frac{1}{\lfloor \frac{1}{2}|G|\rfloor } \right\rceil =k+1=\chi '(G)\ge {\scriptstyle \mathcal {W}}(G), \end{aligned}$$

and hence to $\chi '(G)={\scriptstyle \mathcal {W}}(G)$, i.e., G is elementary. $\square$

As observed, independently, by Andersen [4] and Goldberg [46] Lemma 1.2 can be strengthened as follows, see also [108, Theorem 1.4].

Lemma 1.3

Let G be a critical graph with $\chi '(G)=k+1$ for an integer $k\ge \varDelta (G)$. Then G is elementary if and only if there is an edge $e\in E(G)$, a coloring $\varphi \in {\mathcal {C}^k}(G-e)$ and a vertex set $X\subseteq V(G)$ such that X contains both ends of e and X is both $\varphi$-elementary and strongly $\varphi$-closed.

As pointed out in [108], Goldberg’s conjecture can be stated in different ways:

• 1. Every graph G satisfies $\chi '(G)\in \{{\scriptstyle \mathcal {W}}(G),\varDelta (G),\varDelta (G)+1\}$.

• 2. For any odd integer $m\ge 5$, every graph G satisfying

  $$\begin{aligned} \chi '(G)> \varDelta (G)+1+\frac{\varDelta (G)-2}{m-1} \end{aligned}$$

  (1.4)

  is elementary (Gupta [50]).

• 3. Let G be a critical graph with $\chi '(G)=k+1$ for an integer $k\ge \varDelta (G)+1$, let $e\in E(G)$ be an edge, and let $\varphi \in {\mathcal {C}^k}(G-e)$. Then V(G) is $\varphi$-elementary (Andersen [4]).

• 4. Every critical graph G with $\chi '(G)\ge \varDelta (G)+2$ is of odd order and satisfies $2|E(G)|=(\chi '(G)-1)(|V(G)|-1)+2$ (Critical multigraph conjecture).

Guptas’ conjecture (statement (2)) is a parameterized version of Goldberg’s conjecture. Gupta formulated both (1) and (2), with (2) as a stronger version of (1). It seems that he did not notice that the two are in fact equivalent. By Lemma 1.1, it suffices to prove Guptas’ conjecture for critical graphs. By Shannon’s bound no graph satisfies (1.4) with $m=3$. Up to now Gupta’s conjecture is known to be true for odd m with $5\le m \le 39$. This was proved, for $m=5$ independently by B. Aa. Sørensen (unpublished), Andersen [4], Goldberg [44], and Gupta [50], for $m=7$ independently by B. Aa. Sørensen (unpublished), Andersen [4], and Gupta [50], for $m=9$ by Goldberg [45, 46], and for $m=11$ by Nishizeki and Kashiwagi [84]. All proofs presented by these authors (with the exception of Gupta’s proofs) rely on Lemma 1.3 and use the so-called critical chain method (see [108, Corollary 5.5]). Gupta uses a different approach and derived his results from more general statements about improper edge colorings of graphs. The proof given by Nishizeki and Kashiwagi [84] from 1990 for the case $m=11$ is very long and exploits the critical chain method to its limit. Ten years later Tashkinov [110] used his new method, described in Sect. 2, to give a much shorter proof for the case $m=11$. In 2006 Favrholdt et al. [39] used an extension of Tashkinov methods to established the case $m=13$. The next step $m=15$ was obtained in 2008 by Scheide [98, 99]. A decade later, Chen et al. [18] succeeded to handle the case $m=23$. The case $m=39$ was solved by Chen and Jing [19]. Note that the last result implies the earlier results. So we obtain the following theorem, whose proof relies on Lemma 1.2 and uses an extension of Tashkinov’s recoloring method.

Theorem 1.2

(Chen and Jing) Every graph G satisfies

• (a) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G),\varDelta (G)+1+\frac{\varDelta (G)-2}{38}\}$, and

• (b) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G),\varDelta (G)+1\}$ provided that $\varDelta (G)\le 39$ or $|G|\le 39$.

In the next theorem we present some other approximation results for Goldberg’s conjecture. For a graph G, let L(G) denote the line graph of G; note that $\chi '(G)=\chi (L(G))$. Furthermore, let $g_o(G)$ denote the length of the shortest odd cycle, where $g_o(G)=\infty$ if G contains no odd cycle.

Theorem 1.3

For any graph G the following statements hold:

• (a) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G),\varDelta (G)+\sqrt{(\varDelta (G)-1)/2}\}$.

• (b) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)+2\sqrt{\mu (G) \ln \varDelta (G)}\}$.

• (c) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)+\root 3 \of {\varDelta (G)/2}\}$.

• (d) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)+1, \frac{5 \varDelta (L(G))+8}{6}\}$.

• (e) $\chi '(G)\le \max \{{\scriptstyle \mathcal {W}}(G), \varDelta (G)+1+\frac{\varDelta (G)-2}{g_o(G)-1}\}$.

• (f) $\chi '(G)\le \kappa (G) + \log _{3/2}(\min \{(|G|+1)/3,\kappa (G)\})$ provided that $E(G)\not =\emptyset$.

Statement (a) was obtained in 2008 by Scheide [98, 99] using Tashkinov’s recoloring technique; he also proved that the parameter $\max \{{\scriptstyle \mathcal {W}},\varDelta +\sqrt{(\varDelta -1)/2}\}$ is an efficiently realizable upper bound for the chromatic index (see also [108, Sect. 5.5]). A slightly weaker bound was established by Chen et al. [21]; however, their proof involved an exponential number of recolorings. Statement (b) was proved by Haxell and McDonald [54]; statement (c) was established by Chen et al. [18], statement (d) was obtained by Cranston and Rabern [30], and statement (e) is due to McDonald [76]. For (a)–(e), the proofs used Tashkinov’s method. The inequality in statement (f) is due to Plantholt [88]; it involves the parameter $\kappa =\max \{{\scriptstyle \mathcal {W}},\varDelta \}$. Plantholt’s proof is constructive, but it is based on a splitting technique instead of Tashkinov’s recoloring technique. It would be of much interest to replace the quantity $\root 3 \of {\varDelta (G)/2}$ in the inequality in Theorem 1.3(c) by a logarithmic function of $\varDelta$. One step in this direction was obtained by Haxell and Kierstead [52]; they also used Tashkinov’s method. Further results in this direction were obtained by Chen and Jing [19].

The combined parameter $\kappa =\max \{\varDelta ,{\scriptstyle \mathcal {W}}\}$ can be computed by a polynomial time algorithm, as $\kappa$ is closely related to the fractional chromatic index. Recall the the chromatic index of a graph G is the least integer k such that E(G) can be partitioned into k matchings of G. Let $\mathcal{M}(G)$ denote the set of all matchings of G. Then the chromatic index of a graph G with $E(G)\not =\emptyset$ can be expressed as the solution of a binary LP-problem, namely

$$\begin{aligned} \chi '(G)=\min \left\{ \sum _{M\in \mathcal{M}(G)}x_M \;|\; \sum _{M:e\in M}x_M=1 \text{ for } \text{ all } e\in E(G), x\in \{0,1\}^{\mathcal{M}(G)} \right\} , \end{aligned}$$

where $x_M\in \{0,1\}$ indicates whether or not the matching M is a color class in the edge coloring $x:\mathcal{M}(G)\rightarrow \{0,1\}$. The linear programming relaxation (that is, we replace the set $\{0,1\}$ by the real interval [0, 1]) defines the fractional chromatic number$\chi '^*(G)$, that is,

$$\begin{aligned} \chi '^*(G)=\min \left\{ \sum _{M\in \mathcal{M}(G)}x_M \;|\; \sum _{M:e\in M}x_M=1 \text{ for } \text{ all } e\in E(G), x\in [0,1]^{\mathcal{M}(G)} \right\} . \end{aligned}$$

For a graph G with $E(G)=\emptyset$, we put $\chi '^*(G)=0$. As explained in Schrijver’s book [101] the fractional chromatic index can be computed in polynomial time. From Edmonds’ matching polytope theorem [34] (see also [108, Appendix B]) it follows that every graph G with $|G|\ge 2$ satisfies

$$\begin{aligned} \chi '^*(G)=\max \left\{ \varDelta (G), \max _{X\subseteq V(G), |X|\ge 2}\frac{|E(G[X])|}{\lfloor \frac{1}{2}|X|\rfloor }\right\} . \end{aligned}$$

For a graph G with $|G|\le 2$ we have $\chi '^*(G)=\varDelta (G)$. By definition, $\chi '^*(G)\ge \varDelta (G)$. Consequently, every graph G satisfies $\kappa (G)=\max \{\varDelta (G),{\scriptstyle \mathcal {W}}(G)\}=\lceil \chi '^*(G)\rceil$. If $\chi '^*(G)=\varDelta (G)$, then ${\scriptstyle \mathcal {W}}(G)\le \varDelta (G)$. If $\chi '^*(G)>\varDelta (G)$, then ${\scriptstyle \mathcal {W}}(G)=\lceil \chi '^*(G)\rceil$ and ${\scriptstyle \mathcal {W}}(G)$ can be computed in polynomial time. Consequently, every graph G satisfies the equation

$$\begin{aligned} {\tilde{\kappa }}(G)=\max \{\varDelta (G)+1,{\scriptstyle \mathcal {W}}(G)\}=\max \{\varDelta (G)+1, \lceil \chi '^*(G)\rceil \} \end{aligned}$$

(1.5)

Recently, Chen et al. [22] developed a polynomial-time algorithm that computes ${\scriptstyle \mathcal {W}}(G)$ for each graph G. Hence, Goldberg’s conjecture that $\chi '\le {\tilde{\kappa }}$ implies that the difficulty in determining the chromatic index of a graph G is only (in the case $\chi '^*(G)=\varDelta (G)$) to distinguish between the two cases $\chi '(G)=\varDelta (G)$ and $\chi '(G)=\varDelta (G)+1$.

Using probabilistic arguments, Kahn [64] proved the asymptotic result that, for any graph G,

$$\begin{aligned} \chi '(G) \sim \chi '^*(G) \text{ as } \chi '^*(G) \rightarrow \infty . \end{aligned}$$

Sanders and Steurer [95] used classical recolouring techniques to show that, for any graph G, $\chi '(G)\le \chi '^*(G)+\sqrt{(9 \chi '^*(G))/2}$. As a simple corollary of Theorem 1.3(a) Scheide [98] (see also [108, Theorem 6.2]) could improve this to $\chi '(G)\le \chi '^*(G)+\sqrt{ \chi '^*(G)/2}$. As a corollary of Theorem 1.3(b) Plantholt [88] proved that for any positive real numbers c, d, there exists a positive integer N, so that $\chi '(G)\le \chi '^*(G)+c(\chi '^*(G))^d$ provided that $\chi '^*(G)>N$.

1.3 Seymour’s Exact Conjecture

As emphasized by Haxell et al. [53] one of the main questions in the area of edge colouring is to understand which graphs have an upper bound for the chromatic index$\chi '$that matches the trivial lower bound$\kappa =\max \{{\scriptstyle \mathcal {W}},\varDelta \}$ (see (1.3)). Similarly to the case of simple graphs, we would like to distinguish between graphs whose chromatic index is the same as the trivial lower bound, and those that do not have this property. As proposed in [108, Sect. 6.6], we say that a graph G is first class if $\chi '(G) = \kappa (G)$, and otherwise it is second class. So a graph G is first class if and only if $\chi '(G)=\lceil \chi '^*(G)\rceil$. If Goldberg’s conjecture is true, then a graph is second class if and only if $\chi '(G)=\kappa (G)+1=\lceil \chi '^*(G)\rceil +1=\varDelta (G)+1$ and $\varDelta (G)\ge {\scriptstyle \mathcal {W}}(G)$. Note that a simple graph G satisfying $\chi '(G)=\varDelta (G)+1={\scriptstyle \mathcal {W}}(G)$ is first class in this new classification, but class two in the standard classification. The Petersen graph with a vertex deleted, denoted by $P^*$, is both class two and second class as ${\scriptstyle \mathcal {W}}(P^*)=\varDelta (P^*)=3$, but $\chi '(P^*)=4$ (see [108, page 16]).

In 1977 Erdős and Wilson [38] proved that almost every simple graph is class one. More precisely, if $\mathcal{G}(n,p)$ denotes the binomial random graph model (that is, the probability space consisting of all simple graphs with n labelled vertices, where each possible edge is included independently with probability p), then almost every simple graph in $\mathcal{G}(n,\frac{1}{2})$ has a unique vertex of maximum degree and is therefore class one. Recently, Haxell et al. [53] proved that almost every graph is first class. So let $\mathcal{MG}(n,m)$ denote the probability space consisting of all graphs with vertex set $V=\{1,2, \ldots , n\}$ and m edges, in which m elements from ${ V \atopwithdelims ()2}$ are chosen independently with repetitions. The main result in [53] then says that if $m=m(n)$, then almost every graph in $\mathcal{MG}(n,m)$ is first class; the proof of this result makes extensive use of Tashkinov’s method. As a consequence, Goldberg’s conjecture is true for random graphs.

While random graphs are almost surely first class, only few classes of graphs are known for which it has been proved that all its member are first class. All bipartite graphs are first class (by König’s result) and all ring graphs (i.e., graphs whose underlying simple graphs are cycles) are first class (see [108, Theorem 6.3]). In 1990 Seymour [104] proved that any series parallel graph is first class (see also [108, Theorem 6.31]). In the late 1970s Seymour [102, 103] made the following conjecture.

Conjecture 3

(Seymour’s Exact Conjecture) Every planar graph G is first class, that is, $\chi '(G)=\max \{\varDelta (G),{\scriptstyle \mathcal {W}}(G)\}$.

Note that a graph is planar if and only if its underlying simple graph is planar. The name Exact Conjecture was introduced by Marcotte [74] who verified the conjecture for a subclass of planar graphs; she proved that every graph not containing $K_5^-$ (the $K_5$ minus an edge) or $K_{3,3}$ as a minor is first class. Seymour’s conjecture is a far reaching extension of the Four-Color Theorem. To see this, we need some further notation.

We say that a graph G is an r-graph if $|\partial _G(X)|\ge r$ for every odd subset X of V(G). As $\partial _G(V(G))=\emptyset$, every r-graph with $r\ge 1$ has even order. Note that an r-regular graph G satisfies $\chi '(G)=r$ if and only if G is 1-factorable, that is, E(G) is the union of r perfect matchings. Hence any r-regular graph G with $\chi '(G)=r$ must be an r-graph. The Petersen graph is a 3-graph with $\chi '=4$ and shows that the converse statement is not true. Using a simple parity argument, it is easy to show that a connected cubic graph is a 3-graph if and only if it is bridgeless. A simple calculation (see [108, page 186]) shows that any r-graph satisfies ${\scriptstyle \mathcal {W}}\le r$ and so $\kappa =r$. Hence Seymour’s exact conjecture implies the conjecture that every planar r-graph has an r-edge-coloring and is therefore 1-factorable. While the cases $r=0,1,2$ are trivial, the case $r=3$ states that every bridgeless cubic planar graph has chromatic index 3. By a result of Tait [109] from 1878 this is equivalent to the Four-Color Theorem. The cases $r=4$ and $r=5$ were proved by Guenin [48]. The next case $r=6$ was solved by Dvořák et al. [33] in 2016. In his Master thesis Edwards [35] gave a proof for the case $r=7$, a simpler proof was given by Chudnowsky et al. [27]. Finally, the case $r=8$ was solved by Chudnowsky et al. [28]. All the proofs for the values $r\ge 4$ are based on reductions to the previous case, i.e., the Four-Color Theorem is assumed.

Conjecture 4

(Tutte and Lovász) Every r-graph with $r\ge 3$ not having the Petersen graph as a minor is 1-factorable and hence first class.

The special case $r=3$ of the above conjecture is equivalent to the claim that any cubic bridgeless graph not having the Petersen graph as a minor is 1-factorable; this was proposed by Tutte [111]. The generalization is due to L. Lovász (see the discussion in [108, page 252]). A solution of Tutte’s conjecture is presented in a series of four papers, two papers by Robertson et al. [93, 94], one paper by Edwards et al. [37], and one paper (in preparation) by Sanders and Thomas [96]. The proof method is a variant on the proof of the Four-Colour Theorem given in [92].

1.4 Conjectures Related to the Classification Problem

A majority of the early edge coloring papers is devoted to the Classification Problem for simple graphs. Let G be a simple graph with maximum degree $\varDelta$. By the Vizing-Gupta bound and (1.3) if follows that ${\scriptstyle \mathcal {W}}(G)\le \varDelta +1$ and equality holds if and only if G is an elementary class two graph. Furthermore, a simple calculation (see also [108, Sect. 4.3]) shows that ${\scriptstyle \mathcal {W}}(G)=\varDelta +1$ if and only if G has an induced subgraph H satisfying $|E(H)|>\varDelta \lfloor \tfrac{1}{2}|H| \rfloor$; such an induced subgraph of G is called an overfull subgraph of G. We say that G is an overfull graph if G is an overfull subgraph of itself. Note that any overfull subgraph of G has odd order and the same maximum degree as G. Hence if G has an overfull subgraph, then G is class two. However, the converse statement is not true as the Petersen graph or the graph $P^*$ shows; note that $\varDelta (P^*)=|P^*|/3=3$. In 1986, Chetwynd and Hilton [25] proposed the following conjecture.

Conjecture 5

(Overfull Conjecture) A simple graph G on n vertices and with maximum degree $\varDelta > n/3$ is class one if and only if ${\scriptstyle \mathcal {W}}(G)\le \varDelta$, that is, G contains no overfull subgraph.

Very little is known about this conjecture. Some partial results are discussed in the book [108, page 111] from 2012; not much was added since then. A simple regular graph of odd order is an overfull graph and hence class two. If G is a simple $\varDelta$-regular graph of even order n and $\varDelta \ge 2\lceil n/4 \rceil -1$, then ${\scriptstyle \mathcal {W}}(G)\le \varDelta$ (see [108, Lemma 4.15]), and the overfull conjecture implies that G is 1-factorable. That this may be true was first stated as a conjecture by Chetwynd and Hilton [24, 26] who also proved partial results (see [108, Theorem 4.17]). However, they state that according to G. A. Dirac, this 1-factorization conjecture was already discussed in the 1950s. A notable consequence of this conjecture is that, for any regular simple graph of even order, either the graph or its complement is 1-factorable. That the 1-factorization conjecture is true at least for graphs whose order is large enough was recently proved by Csaba et al. [32].

Theorem 1.4

(Csaba, Kühn, Lo, Osthus, Treglown) There is an integer $n_0$ such that every $\varDelta$-regular simple graph of even order n with $n\ge n_0$ and $\varDelta \ge 2\lceil n/4 \rceil -1$ is class one and hence 1-factorable.

That the bound on the maximum degree in the above theorem is best possible is shown in [32]. If $n \equiv 2 \, \mathrm {(mod} \; 4 \mathrm {)}$ take the disjoint union of two complete graphs each having odd order n / 2; if $n \equiv 0 \, \mathrm {(mod} \; 4 \mathrm {)}$ take the disjoint union of two complete graphs having order $n/2-1$ and $n/2+1$ and delete a Hamilton cycle in the larger complete graph. The best previous result towards Theorem 1.4 is due to Perkovic and Reed [87] (see also [108, Theorem 4.20]); they assumed that $\varDelta \ge (1/2+\varepsilon )n$ and $n\ge n_0(\varepsilon )$. This result was extended by Vaughan [113] to graphs with bounded multiplicity (see [108, Sect. 8.5]), thereby proving an approximation form of the following conjecture due to Plantholt and Tipnis [89].

Conjecture 6

(Multigraph 1-Factorization Conjecture) For every positive integer s, every $\varDelta$-regular graph G of order 2n such that $\mu (G)\le s$ and $\varDelta \ge sn$ is 1-factorable.

Perkovic and Reed as well as Vaughan used probabilistic arguments in their proofs, while Csaba et al. [32] used Szemerédi’s regularity lemma. Using the same approach, they could even prove a much stronger result, thereby confirming the Hamilton Decomposition Conjecture proposed in 1970s by Nash-Williams [82].

Theorem 1.5

(Csaba, Kühn, Lo, Osthus, Treglown) There is an integer $n_0$ such that every $\varDelta$-regular simple graph of even order n with $n\ge n_0$ and $\varDelta \ge n/2$ has an edge-disjoint decomposition into Hamilton cycles and at most one perfect matching.

In searching for structural properties of class two graphs, one can use the critical method. A critical subgraph H of G with $\chi '(H)=\chi '(G)$ is called a critical part of G. By Lemma 1.1(a), every graph has a critical part. The stars are the only critical class one graphs. If H is a critical part of a class two graph G, then $\varDelta (H)+1\le \varDelta (G)+1=\chi '(G)=\chi '(H)\le \varDelta (H)+1$ (by Theorem 1.1(b)) implying that H is a critical class two graph with $\varDelta (H)=\varDelta (G)$. The study of critical class two graphs was initiated by Vizing in the mid 1960s. In his third paper [116] about edge coloring, Vizing established a result about the neighborhood of a critical edge in a class two graph, which became known as Vizing’s Adjacency Lemma.

Theorem 1.6

(Vizing’s Adjacency Lemma) Let G be a class two graph with maximum degree $\varDelta$. If $e\in E_G(x,y)$ is a critical edge of G, then x is adjacent in G to at least $\varDelta -d_G(y)+1$ vertices $v\not =y$ such that $d_G(v)=\varDelta$.

Vizing’s Adjacency Lemma (VAL) is the prototype of all adjacency lemmas established over the years by various researchers; many of these adjacency results, either for class two graphs or for graphs in general, are treated in the book [108]. No doubt Vizing’s adjacency lemma is a useful tool for proving results related to the Classification Problem.

For a graph G, let $G^{[\varDelta ]}$ denote the subgraph of G induced by the vertices having maximum degree in G. It is very common in graph edge coloring to call $G^{[\varDelta ]}$ the core of G. Now consider a critical class two graph G. Then G has a critical part H. As H is a critical class two graph with $\varDelta (H)=\varDelta (G)$, we obtain $H^{[\varDelta ]}\subseteq G^{[\varDelta ]}$ and $\delta (H^{[\varDelta ]})\ge 2$ (by VAL) implying that $G^{[\varDelta ]}$ is not a forest. Hence, every simple graph whose core is a forest is class one. This immediate implication of VAL was rediscovered in 1973 by Fournier [42]. Motivated by this result, Hilton and Zhao investigated the Classification Problem for graphs whose core has maximum degree at most 2; in 1996 they published in [56] the following conjecture.

Conjecture 7

(Core conjecture) Let G be a connected simple graph such that $\varDelta (G)\ge 3$ and $\varDelta (G^{[\varDelta ]})\le 2$. Then G is class two if and only if G is overfull or $G=P^*$.

Let us call a connected class two graph G with $\varDelta (G^{[\varDelta ]})\le 2$ a Hilton graph. From VAL it easily follows that every Hilton graph is critical, $G^{[\varDelta ]}$ is 2-regular, and $\delta (G)=\varDelta (G)-1$ or G is an odd cycle (see [108, Lemma 4.8]). Clearly, $P^*$ is a Hilton graph with $\chi '(P^*)=4$ and $\varDelta (P^*)=3$. Hence the core conjecture is equivalent to the claim that every Hilton graph $G\not =P^*$ with $\varDelta (G)\ge 3$ is overfull and hence elementary. Not much progress has been made since the conjecture was proposed by Hilton and Zhao in 1996. A first breakthrough was achieved in 2003, when Cariolaro and Cariolaro [16] settled the base case $\varDelta =3$. They proved that $P^*$ is the only Hilton graph with maximum degree $\varDelta =3$, an alternative proof was given later by Král’, Sereny, and Stiebitz (see [108, pp. 67–63]). The next case $\varDelta =4$ was recently solved by Cranston and Rabern [31], they proved that the only Hilton graph with maximum degree $\varDelta =4$ is $K_5^-$ ($K_5$ with an edge deleted). The case $\varDelta \ge 5$ is wide open. Partial results supporting the core conjecture were obtained by Akbari et al. [1], by Akbari et al. [2] as well as by Akbari et al. [3]; in the last paper the authors prove the core conjecture for claw-free graphs of even order.

Various authors have established sufficient conditions for simple graphs to be class one by studying its core, the reader may consult [108, Sect. 4.2] or [78]. McDonald and Puleo [78] extend the edge coloring notion of core to t-core and establish a sufficient condition for $(\varDelta +t)$-edge-colorings of graphs having multiple edges.

The main motivation for Vizing to study critical class two graphs is the Classification Problem for simple graphs and the fact that any class two graph contains a critical class two graph with the same maximum degree as a subgraph.

Conjecture 8

(Vizing’s Critical Graph Conjectures) If G is class two and critical, then (a) G has a 2-factor, (b) G has independence number $\alpha (G)\le \tfrac{1}{2}|G|$, and (c) $2|E(G)|\ge (\varDelta (G)-1)|G|+3$ provided that $\varDelta (G)\ge 3$.

The three conjectures are due to Vizing; the first conjecture was published 1965 in [115] and the second and third were published 1968 in [117]. Clearly, any graph G having a 2-factor satisfies $\alpha (G)\le \tfrac{1}{2}|G|$, so (a) implies (b). Furthermore, any graph G with $2|E(G)|\ge (\varDelta (G)-1)|G|+3$ satisfies $\alpha (G)\le (\tfrac{1}{2}+\tfrac{1}{2\varDelta (G)})|G|$. It is folklore, that the three conjectures are true for critical class two graphs that are overfull and hence elementary. If G is such a graph with maximum degree $\varDelta \ge 3$ and $e\in E_G(u,v)$ is an edge of G, then there is a coloring $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ and there are colors $\alpha \in \overline{\varphi }(u)$ and $\beta \in \overline{\varphi }(w)$ (by (1.1)). As $\chi '(G)=\varDelta +1$, $\alpha \not =\beta$. As G is elementary, Lemma 1.2 implies that V(G) is $\varphi$-elementary and hence |G| is odd. Consequently the subgraph H with $V(H)=V(G)$ and $E(H)=E_{\varphi ,\alpha } \cup E_{\varphi ,\beta } \cup \{e\}$ is a 2-factor having exactly one odd cycle and this odd cycle contains the edge e. Clearly, this implies $\alpha (G)\le \tfrac{1}{2}|G|$. Eventually, as each color class has $\lfloor |G|/2\rfloor$ edges, $2|E(G)|\ge 2\varDelta (\lfloor |G|/2\rfloor )+2\ge (\varDelta -1)|G|+3$ as |G| is odd and $\varDelta \le |G|-1$. For critical class two graphs in general, however, none of the three conjectures have been solved.

Not much progress has been made since Vizing proposed his 2-factor conjecture (Conjecture 8(a)). There is a family of results, starting in the 2010s, which assert that a critical class two graph G has a Hamilton cycle provided that $\varDelta (G)\ge s|G|$ for some specific $s\le 1$. Such a result has been obtained by Luo and Zhao [71] for $s=6/7$, by Luo et al. [70] for $s=4/5$, and by Chen et al. [17] for $s=3/4$. Cao et al. [14] proved that every critical class two graph G with $\varDelta (G)\ge \tfrac{2}{3}|G|+12$ has a Hamilton cycle. Chen and Shan [20] used Tutte’s 2-factor theorem to show that any critical class two graph G with $\varDelta (G)\ge \tfrac{1}{2}|G|$ has a 2-factor. Kanno and Shan [65] used the fact that any 2-tough graph with at least three vertices has a 2-factor and proved that any critical class two G having toughness at least 3 / 2 and maximum degree at least $\tfrac{1}{3}|G|$ has a 2-factor. The recent survey by Bej and Steffen [6] provides some equivalent formulation of Vizing’s 2-factor conjecture. In particular, it is proved that it suffices to verify the 2-factor conjecture for critical class two graphs G satisfying $\varDelta (G)\le \delta (G)+1$.

The best result related to Vizing’s independence number conjecture (Conjecture 8(b)) has been obtained by Woodall [121]; he proved that any critical class two graph G satisfies $\alpha (G)\le \tfrac{3}{5}|G|$. A marginal improvement of Woddall’s result has been obtained by Pang et al. [86] under the additional assumption that the number of vertices having degree 2 is at most $2\varDelta -2$. Steffen [107] as well as Cao et al. [15] proved a different sort of approximation to Vizing’s independence number conjecture. The main result in [15] says that for every real integer $\varepsilon \in (0,1)$ there are integers $D(\varepsilon )$ and $d(\varepsilon )$ such that every critical class two graph G with $\varDelta (G)\ge D(\varepsilon )$ and $\delta (G)\ge d(\varepsilon )$ satisfies $\alpha (G)\le (\tfrac{1}{2}+\varepsilon )|G|$.

Vizing’s average degree conjecture (Conjecture 8(c)) has received considerable attention and has been studied quite intensively in edge coloring theory in the recent past. Let $a(\varDelta )$ denote the infimum of the average degree taken over all critical class two graphs having maximum degree $\varDelta$. Vizing’s average degree conjecture implies that $a(\varDelta )>\varDelta -1$ for all $\varDelta \ge 3$. Over the years, several lower bounds for the function $a(\varDelta )$ have been established by various authors (see [108, Chap. 4]). In 2007, Woodall [120] proved that $a(\varDelta )\ge \tfrac{2}{3}(\varDelta +1)$ for $\varDelta \ge 3$, $a(\varDelta )\ge \tfrac{2}{3}(\varDelta +\tfrac{3}{2})$ for $\varDelta \ge 8$, and $a(\varDelta )\ge \tfrac{2}{3}(\varDelta +2)$ for $\varDelta \ge 15$. The first improvement of Woodall’s bound for $\varDelta \ge 56$ was obtained by Cao et al. [13]. Woodall’s result was further improved by Cao and Chen [12] to $a(\varDelta )\ge \tfrac{3}{4}\varDelta -8$ provided that $\varDelta \ge 16$. Cao and Chen also proved that for every real integer $\varepsilon \in (0,1)$ there are integers $D(\varepsilon )$ and $d(\varepsilon )$ such that every critical class two graph G with $\varDelta (G)\ge D(\varepsilon )$ and $\delta (G)\ge d(\varepsilon )$ has average degree at least $\varDelta (1-\varepsilon )$. By Woodall’s bound, $a(3)\ge \tfrac{8}{3}$ and the graph $P^*$ shows that the bound is tight. This result was already proved by Jakobsen [60] in 1974; he conjectured that $P^*$ is the only graph for which the bound holds with equality. That this is indeed the case follows from the result by Cariolaro and Cariolaro [16]. To see this, let G be a critical class two with maximum degree $\varDelta =3$, and let $n_k$ denote the number of k-vertices of G, that is, the vertices having degree k in G. Furthermore, let $n=|G|$ and $m=|E(G)|$. By VAL, $n=n_2+n_3$, each 2-vertex is adjacent to two 3-vertices, and each 3-vertex is adjacent to at most one 2-vertex. Thus $n_3\ge 2n_2$ and for the average degree we then obtain

$$\begin{aligned} \frac{2m}{n}=\frac{1}{n}(2n_2+3n_3)=2+\frac{n_3}{n}\ge \frac{8}{3} \end{aligned}$$

as the last inequality is equivalent to $n_3\ge 2n_2$. So if $\frac{2m}{n}=\frac{8}{3}$, then $n_3=2n_2$ implying that the core of G satisfies $\varDelta (G^{[3]})\le 2$. Consequently, G is a Hilton graph with maximum degree $\varDelta =3$ and so $G=P^*$ by a result of Cariolaro and Cariolaro [16]. Cranston and Rabern [29] proved that any critical class two graph with maximum degree $\varDelta =3$ other than $P^*$ has average degree at least $\frac{46}{17}$. This bound is best possible, as shown by the Hajós join $P_2^*$ of two copies of $P^*$. Woodall [122] proved that any critical class two graph with maximum degree $\varDelta =3$ that is neither a $P^*$ nor a $P_2^*$ has average degree at least $\frac{68}{25}(=2.72)$. In 2008 Miao and Peng [79] proved that $a(4)\ge \tfrac{14}{4}$. In 2016 Cheng et al. [23] used their new adjacency lemma (Lemma 3.4) to give a new proof of this bound, thereby repairing a gap in the original proof. Miao et al. [80] proved that $a(6)\ge \tfrac{66}{13}$, thus improving a previous bound. Li and Wei [69] provide new lower bounds for the average degree of critical class two graphs with maximum degrees from 10 to 14.

The coloring number of a graph G, written $\mathrm{col}(G)$, is 1 plus the maximum minimum degree over all subgraphs of G. Vizing [116] obtained as an immediate consequence of VAL that any class two graph G satisfies $\varDelta (G)\le 2 \mathrm{col}(G)-3$ (see also [108, Theorem 4.3]). For a closed surface$\mathbf{S}$, i.e., a compact, connected 2-dimensional manifold without boundary, let

$$\begin{aligned} \varDelta (\mathbf{S})=\max \left\{ \varDelta (G)\;|\;G\; \text{ is } \text{ a } \text{ graph } \text{ of } \text{ class } \text{ two } \text{ that } \text{ is } \text{ embeddable } \text{ in } \;\mathbf{S}\right\} . \end{aligned}$$

That the maximum always exists follows from Vizing’s result about the coloring number of class two graphs and Heawood’s map color theorem [55] saying that the coloring number of simple graphs that are embeddable in a surface $\mathbf{S}$ can be bounded in terms of its Euler characteristic $\varepsilon (\mathbf{S})$. Since the coloring number of simple planar graphs is at most 6, for the sphere $\mathbf{S}_0$ we obtain $\varDelta (\mathbf{S}_0)\le 9$. Vizing [116] proved that $5\le \varDelta (\mathbf{S}_0)\le 8$. The upper bound follows from VAL combined with a discharging argument (see [108, App. A.2]). The lower bound follows from the fact that the graph obtained from the icosahedron by subdividing any edge is a planar class two graph with maximum degree $\varDelta =5$ as the graph is overfull. Vizing [117] asked whether the right value for $\varDelta (\mathbf{S}_0)$ is five or six. That any planar simple graph with maximum degree 7 is class one was proved, independently, by Grünewald [47], by Sanders and Zhao [97], and by Zhang [124]. So the remaining unsolved case is $\varDelta =6$. It follows from Euler’s formula that Seymour’s exact conjecture implies that $\varDelta (\mathbf{S}_0)=5$. This supports the following conjecture, which is usually attributed to Vizing.

Conjecture 9

(Vizing’s planar graph conjecture) Every simple planar graph with maximum degree $\varDelta =6$ is class one.

Vizing’s planar graph conjecture is unsolved. On the other hand, there is a series of papers, published in recent years, answering the conjecture in the affirmative, provided some additional conditions regarding the absence of cycles of given length is guaranteed, see the papers [59, 63, 83, 119, 123, 126]. There are only few results about $\varDelta (\mathbf{S})$ for surfaces with Euler characteritic $\varepsilon (\mathbf{S})\le 1$; some of these results are mentioned in [108, Chap. 4 and 9]. Wang [118] proved that any simple graph embeddable in a surface of non-negative Euler characteristic is class one if it has no cycle of length $\ell$, for $\ell \in \{3,4,5,6\}$.

A simple graph G is 1-planar if it can be drawn in the plane so that each edge intersects at most one other edge in an interior point. The notion of 1-planar graphs was introduced by Ringel [91] in connection with the problem of coloring the vertices and faces of a plane simple graph in such a way that no two adjacent or incident elements receive the same color. Compared to the class of planar graphs, the Classification Problem for 1-planar graphs have not been extensively studied in the literature. The first result concerning edge colorings of 1-planar graphs is due to Zhang and Wu [130], who proved that every 1-planar graph with maximum degree $\varDelta \ge 10$ is class one. In 2012, Zhang and Liu [128] proved that every 1-planar graph without adjacent triangles and with maximum degree $\varDelta \ge 8$ is class one. They [129] also proved that every 1-planar graph without chordal 5-cycles and with maximum degree $\varDelta \ge 9$ is of class one. On the other hand, Zhang and Liu [129] constructed 1-planar class two graphs with maximum degree 6 or 7, so they posed the following conjecture.

Conjecture 10

(Zhang and Liu) Every simple 1-planar graph with maximum degree $\varDelta \ge 8$ is class one.

Zhang and Wu [125] obtained some new sufficient conditions for 1-planar graphs to be class one; they proved, in particular, that every 1-planar graph with maximum degree $\varDelta \ge 8$ without 5-cycles or without adjacent 4-cycles is class one. Jin and Xu [62] proved that every 1-planar graph with maximum degree $\varDelta \ge 7$ is class one provided that it has neither intersecting triangles nor chordal 5-cycles.

As the Classification Problem for the class $\mathcal{G}$ of all simple graphs is difficult, it is reasonable to search for interesting subclasses of $\mathcal{G}$ for which the Classification Problem can be efficiently solved. Two such subclasses are proposed by the overfull conjecture and the core conjecture. The overfull conjecture combined with the results about the fractional chromatic index imply that, for the subclass $\mathcal{G}^*$ of $\mathcal{G}$ consisting of all simple graphs G with $\varDelta (G)>|G|/3$, the Classification Problem can be solved in polynomial time. On the other hand, as proved by Cai and Ellis [11], to decide whether a simple graph is class one remains NP-complete when restricted to perfect graphs. Nevertheless, the complexity of the Classification Problem is unknown for several well-studied subclasses of $\mathcal{G}$ such as planar simple graphs, co-graphs (i.e., simple graphs not containing $P_4$ as an induced subgraph), join graphs (i.e., simple graphs whose complement is disconnected), chordal graphs (i.e., simple graphs in which every induced cycle is a triangle), and several subclasses of chordal graphs such as split graphs (i.e., simple graphs whose vertex set is the disjoint union of a clique and an independent set), interval graphs (i.e., simple graphs that are intersection graphs of finite closed intervals on the real line), and comparability graphs (i.e., simple graphs that have a transitive orientation). For all these subclasses of $\mathcal{G}$ only partial results related to the Classification Problem have been reported; see e.g. [81] or [73]. Join graphs form a subclass of $\mathcal{G}^*$, but even for this very special subclass no polynomial time algorithm for determining the chromatic index is known. On the other hand, several sufficient conditions for join graphs to be class one are obtained in the last decade, see the recent papers [72, 106, 131]. In 2017, Bismarck de Sousa Cruz et al. [9] proved that if a simple graph G is both a split graph and a comparability graph, then G is class two if and only if G is neighborhood-overfull, that is, G has a overfull subgraph whose vertex set consists of a vertex and its neighborhood. In 2000, de Figueiredo et al. [40] proposed the conjecture that every chordal graph is class two if and only if it neighborhood-overfull. However, even for split graphs this conjecture is not solved.

Let us conclude this section with some recent positive results. In 2016, Zhang [127] completely determined the chromatic index of outer 1-planar graphs, a subclass of simple planar graphs.

In 2018, Zorzi and Zatesko [131] proved that every triangle-free simple graph G with $\varDelta (G)\ge |G|/2$ is class one. The proof uses a modified version of Vizing’s recoloring argument. However, the statement is an immediate consequence of VAL. To see this, assume that G is a triangle-free class two graph of order n and with maximum degree $\varDelta \ge n/2$. Then the core $G^{[\varDelta ]}$ contains a cycle and we choose a shortest cycle C in $G^{[\varDelta ]}$. By assumption $|C|\ge 4$ and C is an induced cycle of G. For a vertex v of C, let $N_v$ be the neighborhood of v in G outside C. Clearly, $|N_v|=\varDelta -2$ for any $v\in V(C)$ and $N_v\cap N_w=\emptyset$ whenever $vw\in E(C)$. Since $2\varDelta \ge n$, this implies that n is even, $|C|=4$, say $C=(x,y,z,u)$. Then $N_x=N_z$, $N_y=N_u$, and $A=N_x\cup \{y,u\}$ and $B=N_y \cup \{x,z\}$ is a bipartition of G. Consequently, G is bipartite and hence class one, a contradiction. It is not known whether the overfull conjecture is true for triangle-free simple graphs.

In 2013, Machado et al. [73] proved that if G is a chordless graph (i.e., a simple graph in which every cycle is an induced subgraph) with $\varDelta (G)\ge 3$, then G is class one. It would be interesting to know whether every graph whose underlying simple graph is chordless is first class. Recall that all ring graphs are first class.

In 2018, Bruhn et al. [10] published a paper dealing with the Classification Problem for simple graphs with given treewidth. If G is a simple graph with treewidth k, then G is in particular k-degenerate, i.e., $\mathrm{col}(G)\le k+1$, and so $\varDelta (G)\ge 2k \;(\ge 2\mathrm{col}(G)-2)$ implies that G is class one (by Vizing’s result mentioned above). In [10] it is proved that every simple graph with treewidth k and maximum degree $\varDelta \ge 2k-1$ is class one. Bruhn et al. [10] proposed the conjecture that every simple graph with treewidth k and maximum degree $\varDelta \ge k+\sqrt{k}$ is class one; they proved that every such graph satisfies $\chi '^*=\varDelta$.

2 Tools, Techniques and Classic Results

How can we prove Goldberg’s conjecture that every graph satisfies the inequality $\chi '\le \max \{{\scriptstyle \mathcal {W}},\varDelta +1\}$? As explained in Sect. 1 we can use the critical method (see Lemma 1.1). So it suffices to show that if G is a critical graph with $\chi '(G)=k+1$ for an integer $k\ge \varDelta (G)+1$, then G is elementary. To prove this, we have to find an edge $e\in E_G(x,y)$, a coloring $\varphi \in {\mathcal {C}^k}(G-e)$ and a vertex set $X\subseteq V(G)$ such that $x,y\in X$ and X is both $\varphi$-elementary and strongly $\varphi$-closed (by Lemma 1.3). In the 1960s Vizing [114, 116] and, independently, Gupta [49] developed a similar technique for finding a set X that is $\varphi$-elementary. Another technique for finding a $\varphi$-elementary set was invented by Kierstaed [66]. A breakthrough was obtained in 2000 by Tashkinov [110], his technique yields a set that is both $\varphi$-elementary and $\varphi$-closed. Until now no method is known for constructing a $\varphi$-elementary set that is also strongly $\varphi$-closed.

Let $\textsc {Ext}$ denote the set of all tuples $(G,e,x,y,\varphi ,k)$ consisting of a graph G, an edge $e\in E_G(x,y)$, and a coloring $\varphi \in {\mathcal {C}^k}(G-e)$ for an integer $k\ge \varDelta (G)$. If $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$, then either we want to find an k-edge-coloring of G, or we want to analyze why such a coloring does not exist. Clearly, both problems are of the same nature. In the later case we may assume that $\chi '(G)=k+1$ implying that e is a critical edge of G and $X=\{x,y\}$ is $\varphi$-elementary; then we want to find a larger $\varphi$-elementary set.

2.1 Vizing’s Fans

Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$. A sequence $F=(v_0,e_1,v_1,e_2, \ldots , e_p,v_p)$ with $p\ge 1$ consisting of distinct edges $e_1, e_2, \ldots , e_p$ and vertices $v_0,v_1, \ldots , v_p$ (not necessarily distinct) is called a $\varphi$-fan starting with (x, e) if $(v_0,v_1)=(x,y)$, $e_1=e$, $e_i\in E_G(v_0,v_i)$ for $i\in \{1,2, \ldots , p\}$ and $\varphi (e_i)\in \overline{\varphi }(v_0,v_1, \ldots , v_{i-1})$ for $i\in \{2,3, \ldots , p\}$. A proof of the following result can be found in [108, Theorem 2.1].

Theorem 2.1

Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$ and let $\chi '(G)=k+1$ with $k\ge \varDelta (G)$. If $F=(v_0,e_1,v_1,e_2, \ldots , e_p,v_p)$ is a $\varphi$-fan starting with (x, e), then the following statement holds:

• (a) If $\alpha \in \overline{\varphi }(x)$ and $\beta \in \overline{\varphi }(v_i)$ for $1\le i \le p$, then $\alpha \not =\beta$ and $v_i$ is an end of the path $P_x(\alpha ,\beta ,\varphi )$.

• (b) $V(F)=\{v_0,v_1, \ldots , v_p\}$ is $\varphi$-elementary.

• (c) If F is a maximal $\varphi$-fan starting with (x, e), then $|V(F)|\ge 3$ and, moreover, $\sum _{v\in V(F),v\not =x} (d_G(v)+\mu _G(x,v)-k)\ge 2$.

The proof of (a) is by contradiction, showing that if (a) is false, then after performing a finite number of Kempe changes we obtain a coloring $\varphi '\in {\mathcal {C}^k}(G-e)$ such that there is a color $\alpha \in \overline{\varphi }'(x) \cap \overline{\varphi }'(y)$ which can be used to color the edge e, contradicting $\chi '(G)=k+1$. Statement (b) is a simple consequence of (a). Statement (c) follows from (b) and (1.1). Here maximal means that F cannot be extended to a larger $\varphi$-fan starting with (x, e). The inequality in statement (c) is referred to as the fan inequality. If $k\ge \varDelta (G)+\mu (G)$, then the fan inequality obviously fails. Hence every critical graph G satisfies $\chi '(G)=k+1\le \varDelta (G)+\mu (G)$. By Lemma 1.1 this proves the Vizing-Gupta bound. To see that the fan inequality implies VAL, assume that G is simple and $k=\varDelta (G)$. Then the fan inequality implies that there is a set Y such that $|Y|\ge 2$, $y\in Y \subseteq N_G(x)$, and $\sum _{v\in Y}(d_G(v)+1-k)\ge 2$. Then $Z=Y{\setminus }\{y\}\not =\emptyset$ and $\sum _{v\in Z}(d_G(v)-\varDelta (G)+1)\ge \varDelta (G)+1-d_G(y)$ implying that Z contains at least $\varDelta (G)+1-d_G(y)$ vertices v with $d_G(v)=\varDelta (G)$, which proves VAL. As explained in [108, Chap. 2], the fan inequality implies also Shannon’s bound and several refinements of the Vizing-Gupta bound as well as several adjacency lemmas. One new refinement of the Vizing-Gupta bound obtained in [108, Theorem 2.5] says that if G is a graph with $|G|\ge 2$, then $\chi '(G)\le \varDelta (G)+\min _{v\in V(G)} \mu (G-v)$. Another refinement of Vizing’s theorem was recently obtained by Puleo [90]; he used his result to establish a special case of Tuza’s conjecture [112] saying that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles of G.

The proof of Theorem 2.1 can be transformed into a polynomial algorithm that colors the edges of any graph G with at most $\varDelta (G)+\mu (G)$ colors. The coloring is constructed step by step using Kempe changes along non-elementary fans, see [108, Chap. 2.5, 5.5]. However, this was already pointed out by Vizing and he made the following suggestion (see [115, 117]).

Conjecture 11

(Vizing’s Interchange Conjecture) An edge coloring of any graph G with $\chi '(G)$ colors can always be obtained from an arbitrary edge coloring of G by a sequence of Kempe changes and suppressing empty color classes.

Some few results about Kempe changes and Kempe equivalence of edge colorings are reported in [108, Chap. 9, $\clubsuit$ 19]. Some more recent results and further references can be found in the papers [7, 8, 85].

2.2 Kierstead Paths and Tashkinov Trees

Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$. A sequence $T=(v_0,e_1,v_1,e_2, \ldots , e_p,v_p)$ with $p\ge 1$ consisting of distinct edges $e_1, e_2, \ldots , e_p$ of G and distinct vertices $v_0,v_1, \ldots , v_p$ of G is called a $\varphi$-tree at e if $e_1=e$, $e_i\in E_G(\{v_0,v_1, \ldots , v_{i-1}\},v_i)$ for $i\in \{1,2, \ldots , p\}$, and $\varphi (e_i)\in \overline{\varphi }(v_0,v_1, \ldots , v_{i-1})$ for $i\in \{2, 3, \ldots , p\}$. If, in addition, $e_i\in E_G(v_{i-1},v_i)$ for $i\in \{1,2, \ldots p\}$, then T is called a $\varphi$-path at e. In 2000 Tashkinov [110] invented the concept of a $\varphi$-tree, which is also referred to as a Tashkinov tree, and proved the following remarkable result, see also [108, Theorems 5.1, 5.3]. For the special case of a $\varphi$-path this result was previously proved by Kierstead [66] with a much easier proof; hence such paths are called Kierstead paths.

Theorem 2.2

(Tashkinov) Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$ and let $\chi '(G)=k+1$ with $k\ge \varDelta (G)+1$. If $T=(v_0,e_1,v_1,e_2, \ldots , e_p,v_p)$ is a $\varphi$-tree at e, then $V(T)=\{v_0,v_1, \ldots , v_p\}$ is $\varphi$-elementary. If moreover T is a maximal $\varphi$-tree at e, then V(T) is $\varphi$-closed, |V(T)|is odd, and

$$\begin{aligned} \varDelta (G)\ge \delta (G[V(T)])\ge (|V(T)|-1)(\chi '(G)-\varDelta (G)-1)+2 \end{aligned}$$

(2.1)

The most difficult part in the proof of Tashkinov’s theorem is to show that V(T) is $\varphi$-elementary. Again, the proof is by contradiction, showing that if V(T) is not $\varphi$-elementary, then there is a sophisticated sequence of Kempe changes that will modify $\varphi$ so that both ends of e have a common missing color, and hence the coloring can be extended to e. The remaining three statements are easy to show, for the second inequality in (2.1) we can use (1.1). If V(T) is not $\varphi$-closed, then there is an edge $e'\in E_G(V(T),v)$ with $v\not \in V(T)$ and $\varphi (e')\in \overline{\varphi }(V(T))$, and so $T'=(T,e',v)$ is a $\varphi$-tree at e, implying that T is not a maximal $\varphi$-tree at e. It is easy to show that the vertex set of a maximal $\varphi$-tree is a unique set completely determined by e and $\varphi$; it is the smallest $\varphi$-closed set containing the two ends of the uncolored edge e. If a maximal $\varphi$-tree has t vertices, then $t\ge 3$ is odd and (2.1) implies that

$$\begin{aligned} \chi '(G)\le \varDelta (G)+1 +\frac{\varDelta (G)-2}{t-1}\le \frac{3\varDelta (G)}{2}. \end{aligned}$$

Let us briefly indicate how Tashkinov’s theorem can be used to prove that every graph satisfies $\chi '\le \max \{{\scriptstyle \mathcal {W}},\frac{5\varDelta +2}{4}\}$. Clearly, it suffices to prove this for critical graphs (by Lemma 1.1). So let G be a critical graph with $\chi '(G)=k+1$ and let $\varDelta =\varDelta (G)$. If $\chi '(G)\le \frac{5\varDelta +2}{4}$ then there is nothing to prove. Otherwise, $k\ge \varDelta +1$ and we choose an edge, say $e\in E_G(x,y)$, and a coloring $\varphi \in {\mathcal {C}^k}(G-e)$. Then $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$ and we can use Tashkinov’s theorem. So let T be a maximal $\varphi$-tree at e and let $t=|V(T)|$. We may choose $\varphi$ so that t is maximum. By Theorem 2.2, V(T) is $\varphi$-elementary and $\varphi$-closed. If $t\ge 5$, then $\chi '(G)\le \frac{5\varDelta +2}{4}$. It remains to consider the case $t=3$. Then T has the form $T=(x,e,y,e',z)$ and $\alpha =\varphi (e')\in \overline{\varphi }(x)$. Let $X=V(T)=\{x,y,z\}.$ If X is strongly $\varphi$-closed, then G is elementary (by Lemma 1.3), that is, $\chi '(G)={\scriptstyle \mathcal {W}}(G)$ as required. So assume that X is not strongly $\varphi$-closed. Then $\partial _G(X)$ contains two edges with the same color, say $\beta$ (such a color is called a defective color). As X is $\varphi$-closed, $\beta$ is present at any vertex of X, so $\partial _G(X)$ contains three edges colored with $\beta$. Then for each vertex $v\in X$ there is an edge $e_v\in E_G(v) \cap \partial _G(X)$ with $\varphi (e_v)=\beta$. As $k\ge \varDelta +1$, it follows from (1.1) that there is a color $\gamma \in \overline{\varphi }(x){\setminus }\{\alpha \}$ (such a color is called a free color). Then $P=P_x(\beta ,\gamma , \varphi )$ is a path where one end is x and the other end is a vertex $u\in V(G){\setminus }X$. Note that no edge in $\partial _G(X)$ is colored with $\gamma$ as X is $\varphi$-closed. Clearly $e_x$ belongs to P and so either P contains both edges $e_y$ and $e_z$ or none of them. In the latter case, $\varphi '=\varphi /P\in {\mathcal {C}^k}(G-e)$ and T is a $\varphi '$-tree with $\beta \in \overline{\varphi }'(x)$ and $\varphi '(e_y)=\varphi '(e_z)=\beta$. Hence we can add the two edges $e_y$ and $e_z$ to T to obtain a $\varphi '$-tree $T'$ with $|V(T')|>t$, a contradiction. It remains to consider the case that both edges $e_y$ and $e_z$ belong to P. Since P starts with x and $e_x$, either y belongs to the subpath xPz or z belongs to the subpath xPy. Let us consider the first case (the second case can be dealt with in a similar way). By (1.1) there is a free color $\delta \in \overline{\varphi }(z)$. Since no edge in $\partial _G(X)$ is colored with $\gamma$ or $\delta$, we can swap the colors in G[X] to obtain a coloring $\phi \in {\mathcal {C}^k}(G-e)$ such that $\gamma$ is missing at z with respect to $\phi$ and so $P'=P_z(\beta ,\gamma ,\phi )=zPu$. Then $\varphi '=\phi /P'\in {\mathcal {C}^k}(G-e)$, T is a $\varphi '$-tree, $\beta \in \overline{\varphi }'(z)$, and $\varphi '(e_x)=\varphi '(e_y)=\beta$. Hence we can add the two edges $e_x$ and $e_y$ to T to obtain a $\varphi '$-tree $T'$ with $|V(T')|>t$, a contradiction. This complete the proof.

To show the usefulness of his method, Tashkinow [110] gave a new proof of the inequality $\chi '\le \max \{{\scriptstyle \mathcal {W}}, \varDelta +1+\frac{\varDelta -2}{10}\}$, a result already obtained by Nishizeki and Kasiwagi [84], but using a complicated and long argument. As before, we consider a critical graph G with $\varDelta =\varDelta (G)$ and $\chi '(G)=k+1$ for $k\ge \varDelta +1$. If G is elementary, there is nothing to prove. So, assuming that G is not elementary, we choose an edge $e\in E_G(x,y)$, a coloring $\varphi \in {\mathcal {C}^k}(G-e)$ and a $\varphi$-tree T, such that the order t of T is maximum. As G is not elementary, there are defective colors. As above, we can modify the coloring $\varphi$ such that $t\ge 5$. Using similar arguments, Tashkinov proved that the coloring can be chosen so that $t\ge 9$. Then he proved, see [108, Proposition 5.11] that there are two vertices $v^1,w^1\in V(G){\setminus }V(T)$ such that $X=V(T)\cup \{v^1,w^1\}$ is $\varphi$-elementary and $|\overline{\varphi }(X)|\le k-1$ (so one color is present at any vertex of X). Using (1.1), we then obtain

$$\begin{aligned} |\overline{\varphi }(X)|=\sum _{v\in X}|\overline{\varphi }(v)|=2+\sum _{v\in X}(k-d_G(v))\ge 2+|X|(k-\varDelta ). \end{aligned}$$

Since $|X|=t+2$ and $|\overline{\varphi }(X)|\le k-1$, this leads to

$$\begin{aligned} t\le \frac{k-3}{k-\varDelta }-2 = \frac{\varDelta -3}{k-\varDelta }-1. \end{aligned}$$

As $t\ge 9$, we obtain that $\chi '(G)=k+1\le \varDelta +1+\frac{\varDelta -2}{10}$, which completes the proof of the above inequality. Furthermore (see [108, Proposition 5.11]), there is a vertex $v^2\in V(T)$ such that all colors in $\overline{\varphi }(v^2)$ are used on T (i.e., for each $\alpha \in \overline{\varphi }(v^2)$ there is an edge $e'$ in T with $\varphi (e')=\alpha$), and hence at least $k-\varDelta +1$ colors are used on T. On the other hand, it is not difficult to show that T can be chosen so that each color, except one, is used on T at least two times and hence at most $\frac{t-1}{2}$ colors are used on T (see [108, Theorem 5.4]). This gives $2(k-\varDelta )+3\le t \le \frac{\varDelta -3}{k-\varDelta }-1$, and hence $\chi '(G)=k+1\le \varDelta +\sqrt{(\varDelta -1)/2}$. This shows that $\chi '\le \max \{{\scriptstyle \mathcal {W}}, \varDelta +\sqrt{(\varDelta -1)/2}\}$. This result was first obtained in 2008 by Scheide [98, 99] (see also [108, Theorem 5.19]).

The first method for extending a maximal Tashkinov tree to an even larger $\varphi$-elementary set was already developed by Tashkinov himself. Further extensions of Tashkinov trees were introduced by Favrholdt et al. [39] as well as by Scheide [99] (see also [108, Chap. 5,6]). Chen et al. [21] introduced so-called Vizing-Kierstead-Taskinov trees to show that $\chi '\le \max \{{\scriptstyle \mathcal {W}},\varDelta +1+\sqrt{\varDelta /2}\}$. Asplund and McDonald [5] constructed an elementary graph and a colouring where density cannot be captured by a Tashkinov tree, even with an unlimited number of Kempe changes; they also discussed a new type of an extension of Tashkinov trees. Chen et al. [18] made the next step towards a solution of Goldberg’s conjecture; they introduced the notion Extension of a Tashkinov Tree (ETT) and used this concept to prove $\chi '\le \max \{{\scriptstyle \mathcal {W}},\varDelta +\root 3 \of {\varDelta (G)/2}\}$ as well as $\chi '\le \max \{{\scriptstyle \mathcal {W}},\varDelta +1+\frac{\varDelta -2}{22}\}$. The later inequality was further improved by Chen and Jing [19] by using ETTs, see Theorem 1.2.

2.3 Short Kierstead Paths and Adjacency Lemmas

The method of Tashkinov trees works for graphs with $\chi '\ge \varDelta +2$, so it cannot be applied to the Classification Problem for simple graphs. However, Kierstead’s argument also works for graphs with $\chi '\ge \varDelta +1$, provided we add a degree condition for the vertices of the Kierstead path; this was first pointed out by Zhang [124] (see also [108, Theorem 3.1]).

Theorem 2.3

(Kierstead) Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$ and let $\chi '(G)=k+1$ with $k\ge \varDelta (G)$. If $T=(v_0,e_1,v_1,e_2, \ldots , e_p,v_p)$ is a $\varphi$-path at e such that $d_G(v_i)\le k$ whenever $2 \le i \le p$, then V(T) is $\varphi$-elementary. As a consequence, $d_G(v_0)+d_G(v_1)+ \cdots + d_G(v_p)\ge p\varDelta (G)+2$.

The degree condition in the above theorem may not always be satisfied in class two graphs, which limits the application of Kierstaed paths in general. However, a short Kierstaed path is always nearly elementary without assuming any degree condition. The next theorem was obtained by Kostochka and Stiebitz and first published 2006 in the technical report [39] and later in [108, Theorem 3.3]).

Theorem 2.4

(Kostochka, Stiebitz) Let G be a graph with maximum degree $\varDelta$ and $\chi '(G)=\varDelta +1$. Let $e\in E(G)$ be a critical edge and $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ be a coloring. If $K=(v_0,e_1,v_1,e_2,v_2,e_3,v_3)$ is a $\varphi$-path at e, then V(K) is $\varphi$-elementary, unless $d_G(v_1)=d_G(v_3)=\varDelta$. Furthermore, if $\varGamma =\overline{\varphi }(v_0)\cup \overline{\varphi }(v_1)$, then $|\overline{\varphi }(v_3) \cap \varGamma |\le 1$. As a consequence, $d_G(v_0)+d_G(v_1)+d_G(v_2)\ge 2\varDelta +2$ and, moreover, $d_G(v_0)+d_G(v_1)+d_G(v_2)+d_G(v_3)\ge 3\varDelta +1$ with equality only if $d_G(v_1)=d_G(v_3)=\varDelta$.

VAL yields some useful information about the neighborhood of a vertex in a class two graph that is incident with a critical edge. The above theorem is useful when dealing with the second neighborhood of such a vertex. As demonstrated in [108, Sect. 4.4] several adjacency lemmas dealing with the second neighborhood can be derived from Theorem 2.4. Let us mention two important such adjacency lemmas. The following adjacency lemma is an enhancement of a result due to Sanders and Zhao [97]; the proof given in [108] uses the fact that a critical edge in a class two graph can be extended to several short Kierstead paths.

Lemma 2.1

Let G be a class two graph with maximum degree $\varDelta$, and let $e\in E_G(x,y)$ be a critical edge of G. Then there are at least $\varDelta -d_G(y)+1$ vertices $z\in N_G(x){\setminus }\{y\}$ with $d_G(z)\ge 2\varDelta -d_G(x)-d_G(y)+2$ satisfying the following: There are at least $2\varDelta +1-d_G(x)-d_G(y)$ vertices $u\in N_G(z){\setminus }\{x\}$ such that $u=y$, or $d_G(x)=d_G(z)=\varDelta$ and $d_G(u)\ge \varDelta -d_G(y)+1$, or $d_G(u)\ge 3\varDelta -d_G(x)-d_G(y)-d_G(z)+2$.

Before we discuss a further adjacency lemma, we need some more notation. Let G be a graph with maximum degree $\varDelta$, and let q be a positive real number. For a pair (x, y) of distinct vertices of G, define

$$\begin{aligned} \sigma ^G_q(x,y)=|\left\{ z\in N_G(y){\setminus }\{x\} \;|\; d_G(z)\ge q \right\} | \end{aligned}$$

and

$$\begin{aligned} \sigma ^G(x,y)=|\left\{ z\in N_G(y){\setminus }\{x\} \;|\; d_G(x)+d_G(y)+d_G(z)\ge 2\varDelta +2 \right\} |. \end{aligned}$$

So $\sigma (x,y)=\sigma _q(x,y)$ with $q=2\varDelta +2-d_G(x)-d_G(y)$. As usual, we omit the index G if it is clear to which graph we refer. By VAL, if xy is a critical edge of a class two graph with maximum degree $\varDelta$, then $\sigma _{\varDelta }(x,y)\ge \varDelta -d_G(x)+1$. Woodall [120] studied $\sigma (x,y)$ and proved that if xy is a critical edge of a class two graph with maximum degree $\varDelta$, then there are at least $\varDelta -\sigma (x,y)\ge \varDelta -d(y)+1$ vertices $z\in N(x){\setminus }\{y\}$ such that $\sigma (x,z)+\sigma (x,y)\ge 2\varDelta -d(x)$. A proof of this result based on short Kierstead paths is given in [108, Theorem 4.31]. As a consequence, Woodall obtained the following lemma (see [108, Corollary 4.32,4.33]).

Lemma 2.2

(Woodall) Let G be a critical class two graph with maximum degree $\varDelta$, let $x \in V(G)$, let

$$\begin{aligned} p_{\mathrm {min}}=\min _{y\in N_G(x)}\sigma _G(x,y)-\varDelta +d_G(x)-1 \text{ and } p=\min \left\{ p_{\mathrm {min}}, \left\lfloor \frac{1}{2}d_G(x)\right\rfloor -1\right\} . \end{aligned}$$

Then $0\le p_{\mathrm {min}}\le d_G(x)-2$, and x is adjacent to at least $d_G(x)-p_{\mathrm {min}}-1$ vertices z such that $\sigma (x,z)\ge \varDelta -p_{\mathrm {min}}-1$. As a consequence, x has at least $d_G(x)-p-1$ neighbors y such that $\sigma (x,y)\ge \varDelta -p-1$.

Woodall’s proof in [120] that $a(\varDelta )\ge \tfrac{2}{3}(\varDelta +1)$ uses only a simple discharging rule, VAL and the above result, see also [108, Theorem 4.40]. Also Woodall’s proof in [121] that every class two graph G satisfies $\alpha (G)<\tfrac{3}{5}|G|$ uses only these ingredients. It requires improved adjacency lemmas to improve these results.

3 Improved Adjacency Lemmas

One approach to prove that $a(\varDelta )\ge q$ with $q=q(\varDelta )$ is to use the discharging method. So we consider an arbitrary critical class two graph G such that $\varDelta =\varDelta (G)$, $n=|G|$ and $m=|E(G)|$. Our aim is to show that $\tfrac{2m}{n}\ge q$. To this end we apply the discharging method. The initial charge is $M(v)=d(v)$ for all $v\in V(G)$. Then the total charge assigned is 2m. We now redistribute the charge according to the following rule: each vertex u with $d(u)>q$ distributes is surplus $d(u)-q$ equally among all neighbors $v\in N(u)$ with $d(v)<q$. Denote the resulting charge on each vertex $v\in V(G)$ by $M'(v)$. Then for every vertex v with $d(v)<q$, we obtain

$$\begin{aligned} M'(v)=d(v)+\sum _{u\in N(v):d(u)> q}\frac{d(u)-q}{d(u)-\sigma _q(v,u)}. \end{aligned}$$

Our aim is to prove that $M'(v)\ge q$ for all vertices v of G. Then $2m=\sum _{v\in V(G)}M(v)=\sum _{x\in V(G)}M'(v)\ge qn,$ and hence $\tfrac{2m}{n}\ge q$ as required. That $M'(v)\ge q$ is certainly the case when $d(v)\ge q$. So we only need to consider vertices v with $d(v)<q$. If $d(v)=2$, then VAL implies that every vertex at distance 1 or 2 from v has degree $\varDelta$, and so each neighbor of v sends $\varDelta -q$ to v, which gives $M'(v)= 2+2(\varDelta -q)\ge q$, provided that $q\le \tfrac{2}{3}(\varDelta +1)$. Woodall [120] used this approach with $q=\tfrac{2}{3}(\varDelta +1)$ and succeeded to show that $M'(v)\ge q$ for all $v\in V(G)$ by using Lemma 2.2. If $q>\tfrac{2}{3}(\varDelta +1)$, then a vertex v of small degree has to receive charge also from vertices having distance 2 to v. In this case, however, we need improved adjacency lemmas to show that $M'(v)\ge q$ for all $v\in V(G)$.

3.1 Short Brooms

Tashkinov trees work very well for graphs with $\chi '\ge \varDelta +2$, but it does not apply to class two graphs. Recently, Chen et al. [17] used special Tashkinov trees to obtain improved adjacency lemmas for critical class two graphs. A broom is a simple graph obtained from a star by subdividing one edge, if this edge is subdivided exactly once the broom is said to be short.

Let $(G,e,x,y,\varphi ,k)\in \textsc {Ext}$, and let $T=(x,e,y,e',z,e_1,v_1, \ldots , e_p,v_p)$ be a $\varphi$-tree at e. We call T a $\varphi$-broom at (x, y) if $e'\in E_G(y,z)$, $e_i\in E_G(z,v_i)$ and $\varphi (e_i)\in \overline{\varphi }(x,y,z,v_1, \ldots , v_{i-1})$ for $i\in \{1,2, \ldots , p\}$. We call T a simple$\varphi$-broom at (x, y) if $e'\in E_G(y,z)$, $e_i\in E_G(z,v_i)$ and $\varphi (e_i)\in \overline{\varphi }(x,y,z)$ for $i\in \{1,2, \ldots , p\}$.

Simple brooms were introduced by Chen et al. [17]. They proved that if G is a graph with maximum degree $\varDelta$ and $\chi '(G)=\varDelta +1$, $e\in E_G(x,y)$ is a critical edge and $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ is a coloring, then the vertex set of a simple $\varphi$-broom at (x, y), say $T=(x,e,y,e',z,e_1,v_1, \ldots , e_p,v_p)$, is $\varphi$-elementary, provided that (1) $d_G(z)<\varDelta$ or (2) $d_G(y)<\varDelta$ and $|\overline{\varphi }(x,y)|\ge 4$. The following result shows that brooms in general yield elementary sets even under a weaker assumption.

Theorem 3.1

Let G be a graph with maximum degree $\varDelta$ and $\chi '(G)=\varDelta +1$, let $e\in E_G(x,y)$ be a critical edge, let $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ be a coloring, and let $T=(x,e,y,e',z,e_1,v_1, \ldots , e_p,v_p)$ be a $\varphi$-broom at (x, y) such that $\min \{d_G(y),d_G(z)\}$$<\varDelta$. Then V(T) is $\varphi$-elementary. Furthermore, if the $\varphi$-broom T is a maximal $\varphi$-broom at (x, y) such that $\min \{d_G(y),d_G(z)\}$$<\varDelta$, then

$$\begin{aligned} \sum _{v\in V(T){\setminus }\{z\}}(d_G(v)+\mu _G(z,v)-\varDelta )\ge 2. \end{aligned}$$

(3.1)

Proof

By a bad pair we mean a pair $(T,\varphi )$ consisting of a coloring $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ and $\varphi$-broom T at (x, y) such that the degree condition holds, but V(T) is not $\varphi$-elementary. Our aim is to show that there is no bad pair. The proof is by reductio ad absurdum. So suppose that there is a bad pair. Then we choose a bad pair $(T,\varphi _0)$, say $T=(x,e,y,e',z,e_1,v_1, \ldots , e_p,v_p)$, such that p is minimum. Let $\mathcal {C}$ denote the set of all colorings $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ such that T is a $\varphi$-broom at (x, y) and V(T) is not $\varphi$-elementary. Clearly, $\varphi _0\in \mathcal {C}$. Now consider an arbitrary coloring $\varphi \in \mathcal {C}$. For $i\in \{1,2, \ldots , p\}$, $T_i=(x,e,y,e',z,e_1,v_1, \ldots , e_i,v_i)$ is a $\varphi$-broom at (x, y) and, moreover, $T_1$ is a $\varphi$-path at e. By the minimality of p and Theorem 2.4, this implies that $p\ge 2$ and $V(T_{p-1})=\{x,y,z,v_1, v_2, \ldots , v_{p-1}\}$ is $\varphi$-elementary. As V(T) is not $\varphi$-elementary, there is a pair $(u,\gamma )$ such that $u\in V(T_{p-1})$ and $\gamma \in \overline{\varphi }(v_p)\cap \overline{\varphi }(u)$. Let $I_{\varphi }$ denote the set of all such pairs.

First, we claim that there is a coloring $\varphi \in \mathcal {C}$ such that (+) $I_{\varphi }$ contains a pair $(u,\gamma )$ with $u\in \{x,y,z\}$. To this end, let $\varphi \in \mathcal {C}$ be an arbitrary coloring. If (+) is not satisfied, then there is a pair $(u,\gamma )\in I_{\varphi }$ such that $u=v_i$ with $1\le i \le p-1$. Let $\varGamma _{\varphi }=\{\varphi (e_1),\varphi (e_2), \ldots , \varphi (e_p)\}$. Clearly, $\varphi (e')\in \overline{\varphi }(x)$, $\varphi (e_1)\in \overline{\varphi }(x,y)$ and $\varGamma _{\varphi }\cup \{ \varphi (e') \} \subseteq \varphi (z)$. By the minimality of p, it follows that $|\overline{\varphi }(x,y,z) \cap \varGamma _{\varphi }|\le 2$. Let $\alpha =\varphi (e')$, $\alpha _1=\varphi (e_1)$, and $\varGamma '= \varGamma _{\varphi } \cap \overline{\varphi }(x,y,z)$. As $\min \{d_G(y),d_G(z)\}<\varDelta$ and the edge e between x and y is uncolored, it follows from (1.1) that $|\overline{\varphi }(x,y,z)|\ge 3$. First consider the case when there is no color in $\overline{\varphi }(x,y,z){\setminus }(\varGamma ' \cup \{\alpha \})$. Then $\overline{\varphi }(x,y,z)=\varGamma ' \cup \{\alpha \}$ and $|\varGamma '|=2$. This implies that $\overline{\varphi }(z)=\emptyset$ and so $d_G(z)=\varDelta$ (by (1.1)). Consequently, $d_G(y)\le \varDelta -1$ and, as $|\overline{\varphi }(x,y)|=3$, it then follows that $\overline{\varphi }(x)=\{\alpha \}$ and $\overline{\varphi }(y)=\varGamma '$. Now color e with $\alpha$ and let $e'$ uncolored. As $\alpha \in \overline{\varphi }(x)$, this results in a coloring $\varphi '\in {\mathcal {C}^{\varDelta }}(G-e')$ such that $F=(z,e',y,e_1,v_1, \ldots , e_p,v_p)$ is a $\varphi '$-fan starting with $(z,e')$. As $\gamma \in \overline{\varphi }(v_i) \cap \overline{\varphi }(v_p)=\overline{\varphi }'(v_i) \cap \overline{\varphi }'(v_p)$, V(F) is not $\varphi '$-elementary, a contradiction to Theorem 2.1. It remains to consider the case that there is a color $\delta \in \overline{\varphi }(x,y,z){\setminus }(\varGamma ' \cup \{\alpha \})$. As $V(T_{p-1})$ is $\varphi$-elementary, there is a unique vertex $w\in \{x,y,z\}$ such that $\delta \in \overline{\varphi }(w)$. Clearly, $\delta \not =\gamma$ and neither $\delta$ nor $\gamma$ belong to $\varphi (E(T_i))$. Let $P=P_w(\gamma ,\delta ,\varphi )$. If $u=v_i$ does not belong to P, then $\varphi '=\varphi /P\in {\mathcal {C}^{\varDelta }}(G-e)$ and $T_i$ is a $\varphi '$-broom at (x, y) such that $\gamma \in \overline{\varphi }'(u)\cap \overline{\varphi }'(w)$, and so $V(T_i)$ is not $\varphi '$-elementary, contradicting the minimality of p. This shows that u belongs to P. Then u does not belong to $P'=P_{v_p}(\gamma ,\delta ,\varphi )$ and so $\varphi '=\varphi /P'\in {\mathcal {C}^{\varDelta }}(G-e)$ and T is a $\varphi '$-broom at (x, y) such that $\delta \in \overline{\varphi }'(w) \cap \overline{\varphi }'(v_p)$. Consequently, $\varphi '\in \mathcal {C}$ and $(w,\delta )\in I_{\varphi }$ with $w\in \{x,y,z\}$. This proves the claim.

Let $\mathcal {C}'$ denote the set of all colorings $\varphi \in \mathcal {C}$ such that there is a pair $(u,\gamma )\in I_{\varphi }$ with $u\in \{x,y,z\}$, and let $I_{\varphi }'$ denote the set of all such pairs. By the above claim, $\mathcal {C}'\not =\emptyset$ and $I_{\varphi }'\not =\emptyset$ for all $\varphi \in \mathcal {C}'$.

Now let $\varphi \in \mathcal {C}'$ be an arbitrary coloring and let $(u,\gamma )\in I_{\varphi }'$ be an arbitrary pair. Then $u\in \{x,y,z\}$ and $\gamma \in \overline{\varphi }(u)\cap \overline{\varphi }(v_p)$ By the minimality of p, it then follows that $\varphi (e_1)\in \overline{\varphi }(x,y)$ and $\varphi (e_i)\in \overline{\varphi }(v_{i-1})$ for $i\in \{2, 3, \ldots , p \}$. Consequently, $\varGamma _{\varphi } \cap \overline{\varphi }(x,y)=\{\varphi (e_1)\}$. First, we claim that $u\not =z$. For otherwise, we can color $e_p$ with $\gamma$, which leads to a coloring $\varphi '\in {\mathcal {C}^{\varDelta }}(G-e)$ such that $T_{p-1}$ is a $\varphi '$-broom at (x, y) and $\varphi (e_p)\in \overline{\varphi }'(z)\cap \overline{\varphi }'(v_{p-1})$, contradicting the minimality of p. Hence, $u\in \{x,y\}$ as claimed. Next, we claim that the color $\alpha _1=\varphi (e_1)$ belongs to $\overline{\varphi }(x)$. Otherwise, $\alpha _1\in \overline{\varphi }(y)$ and we color e with $\alpha =\varphi (e')$ and let $e'$ be uncolored. As $\alpha \in \overline{\varphi }(x)$, this results in a coloring $\varphi '\in {\mathcal {C}^{\varDelta }}(G-e')$ such that $\varphi '(e_i)=\varphi (e_i)$ and $\overline{\varphi }'(v_i)=\overline{\varphi }(v_i)$ for $i\in \{1,2, \ldots , p\}$; moreover, $\alpha \in \overline{\varphi }'(z)$, $\alpha _1\in \overline{\varphi }'(y)$ and $\gamma \in \overline{\varphi }'(u) \cap \overline{\varphi }'(v_p)$. Consequently, $F=(z,e',y,e_1,v_1 \ldots , e_p,v_p)$ is a $\varphi '$-fan starting at $(z,e')$ and so $V(F')$ is $\varphi '$-elementary (by Theorem 2.1). Then $\gamma \in \overline{\varphi }'(x)$, $u=x$ and so $F'=(y,e',z,e,x)$ is a $\varphi '$-fan starting at $(y,e')$. As $\min \{d_G(y),d_G(z)\}<\varDelta$, there is a pair $(\beta ,w)$ with $w\in \{y,z\}$ and $\beta \in \overline{\varphi }'(w){\setminus }\{\alpha , \alpha _1\}$. Note that $\gamma , \beta \not \in \{\alpha , \alpha _1, \varphi '(e_2), \ldots , \varphi '(e_p)\}$. Let $P=P_w(\beta ,\gamma ,\varphi ')$. If $w=z$, then $v_p$ belongs to P (by Theorem 2.1(a) applied to F) and, hence, $\phi =\varphi '/P_x(\beta ,\gamma ,\varphi ')\in {\mathcal {C}^{\varDelta }}(G-e')$ such that $F'$ is a $\phi$-fan that is not $\phi$-elementary as $\beta$ is missing at x and z, contradicting Theorem 2.1. If $w=y$, then x belongs to P (by Theorem 2.1(a) applied to $F'$) and, hence, $\phi =\varphi '/P_{v_p}(\beta ,\gamma ,\varphi ')\in {\mathcal {C}^{\varDelta }}(G-e')$ such that F is a $\phi$-fan that is not $\phi$-elementary as $\beta$ is missing at y and $v_p$, contradicting Theorem 2.1. This proves the claim that $\alpha _1\in \overline{\varphi }'(x)$.

Now, we claim that there is a coloring $\varphi \in \mathcal {C}'$ such that $I_{\varphi }$ contains a pair $(y,\gamma )$. To this end, let $\varphi \in \mathcal {C}'$ and let $(u,\gamma )\in I_{\varphi }'$. If $u=y$, there is nothing to prove. If $u\not =y$, then, by the above claims, $u=x$ and the colors $\alpha$ and $\alpha _1=\varphi (e_1)$ belong to $\overline{\varphi }(x)$. As $\gamma \in \overline{\varphi }(x)$, too, there is a color $\beta \in \overline{\varphi }(y)$ and, therefore, $\beta \not \in \overline{\varphi }(x)$ implying that $\beta$ is not used on T. Furthermore, $P=P_x(\beta ,\gamma ,\varphi )$ is a path joining x and y, and $P'=P_{v_p}(\beta ,\gamma ,\varphi )$ is a path where one end is $v_p$ and the other end is a vertex not belonging to $V(T_{p-1})$. Consequently, $\varphi '=\varphi /P'\in {\mathcal {C}^{\varDelta }}(G-e)$ is a coloring such that $\overline{\varphi }'(w)=\overline{\varphi }(w)$ for all $w\in V(T_{p-1})$ and $\beta \in \overline{\varphi }'(y)\cap \overline{\varphi }'(v_p)$. Hence, T is a $\varphi '$-broom at (x, y) and, therefore, then $\varphi '\in \mathcal {C}'$ and $(y,\beta )\in I_{\varphi '}$ as claimed.

To finish the proof of the theorem, choose a coloring $\varphi \in \mathcal {C}'$ and a pair $(y,\gamma )\in I_{\varphi }$. Then $\alpha =\varphi (e')$ belongs to $\overline{\varphi }(x)$ and, as proved above, $\alpha _1=\varphi (e_1)$ belongs to $\overline{\varphi }(x)$. As $\gamma \in \overline{\varphi }'(y)$, $\gamma \not \in \overline{\varphi }(x)$ and, hence, $\gamma$ is not used on T. Furthermore, $\alpha _p=\varphi (e_p)\in \overline{\varphi }(v_{p-1})$ and we claim that $v_{p-1}$ belongs to the path $P=P_y(\alpha _p,\gamma ,\varphi )$, and is therefore an end of P. For otherwise, $\varphi '=\varphi /P\in {\mathcal {C}^{\varDelta }}(G-e)$ and $T_{p-1}$ is a $\varphi '$-broom an (x, y) such that $\alpha _p\in \overline{\varphi }'(v_{p-1}) \cap \overline{\varphi }'(y)$, contradicting the minimality of p. Consequently, neither y nor $v_{p-1}$ belong to $P'=P_{v_{p}}(\alpha _p,\gamma ,\varphi )$ and so $P'$ is a path containing $e_p$ and joining $v_p$ with a vertex not belonging to V(T). Hence $\varphi '=\varphi /P'\in {\mathcal {C}^{\varDelta }}(G-e)$ such that $\varphi '(e')=\varphi (e')=\alpha$, $\varphi '(e_i)=\varphi (e_i)$ and $\overline{\varphi }'(v_i)=\overline{\varphi }(v_i)$ for $i \in \{1,2, \ldots , p-1\}$, $\overline{\varphi }'(w)=\overline{\varphi }(w)$ for $w\in \{x,y,z\}$, $\varphi '(e_p)=\gamma \in \overline{\varphi }'(y)$, and $\alpha _p\in \overline{\varphi }'(v_p)\cap \overline{\varphi }'(v_{p-1})$. Consequently, $T_{p-1}$ is a $\varphi '$-broom at (x, y) and $K=(x,e,y,e',z,e_p,v_p)$ is a $\varphi '$-path at e. As $\min \{d_G(y),d_G(z)\}<\varDelta$, it follows from (1.1) that there is a pair $(w,\beta )$ such that $w\in \{x,y,z\}$ and $\beta \in \overline{\varphi }'(w){\setminus }\{\alpha ,\alpha _1,\gamma \}$. Consequently, ${\tilde{P}}=P_w(\alpha _p,\beta ,\varphi ')$ is a path where one end is w and the other end is a vertex $w'\not =w$, and $\phi =\varphi '/{\tilde{P}}\in {\mathcal {C}^{\varDelta }}(G-e)$. If $w'\not =v_{p-1}$, then $T_{p-1}$ is a $\phi$-broom at (x, y) such that $\beta$ is missing at w and $v_{p-1}$, contradicting the minimality of p (note that neither $\beta$ nor $\alpha _p$ are used on $T_{p-1}$ with respect to the coloring $\varphi '$). If $w'=v_{p-1}$ then K is a $\phi$-path such that $\beta$ is missing at w and $v_p$, a contradiction to Theorem 2.4. This completes the proof that V(T) is elementary.

Now assume that $T=(x,e,y,e',z,e_1,v_1 \ldots , e_p,v_p)$ is a maximal $\varphi$-broom at (x, y) such that $\min \{d_G(y),d_G(z)\}<\varDelta$. Then V(T) is $\varphi$-elementary. Let $\varGamma =\overline{\varphi }(x,y,v_1, \ldots , v_p)$ and $\varGamma '=\{\varphi (e'),\varphi (e_1), \ldots , \varphi (e_p)\}$. As T is a $\varphi$-broom, we obtain $\varGamma ' \subseteq \varGamma$. If $\beta \in \varGamma {\setminus }\varGamma '$, then $\beta \in \varphi (z)$ (as V(T) is $\varphi$-elementary) and there is an edge ${\tilde{e}}\in E_G(z,\{x,y,v_1, v_2, \ldots , v_p\})$ such that $\varphi ({\tilde{e}})=\beta$ (as T is a maximal $\varphi$-broom at (x, y)). Hence, $m=|\varGamma |-|\varGamma '|$ satisfies (*) $m+p+1\le \mu _G(z,x)+\mu (z,y)+\mu _G(z,v_1)+\cdots + \mu _G(z,v_p)$. As V(T) is $\varphi$-elementary, it then follows that $m+p+1=|\varGamma |=\sum _{v\in X}|\overline{\varphi }(v)|$ with $X=\{x,y,v_1, \ldots , v_p\}$. Using (1.1) and (*) we easily obtain Eq. (3.1). $\square$

The following statement is an immediate consequence of Theorem 3.1, in particular of the broom equation (3.1).

Corollary 3.2

Let G be a class two graph graph with maximum degree $\varDelta$, let $e\in E_G(x,y)$ be a critical edge, let $\varphi \in {\mathcal {C}^{\varDelta }}(G-e)$ be a coloring. Assume that $z\in N(y){\setminus }\{x\}$ and $\varphi (yz)\in \overline{\varphi }(x)$. If $\min \{d_G(y),d_G(z)\}<\varDelta$, then $N(z){\setminus }\{x,y\}$ contains at least $2\varDelta -d(x)-d(y)+1-\mu (z,x)$ vertices of maximum degree.

3.2 New Adjacency Lemmas

In the sequel, let G be a class two graph with maximum degree $\varDelta$, and let xy be a critical edge with $x,y\in V(G)$. If $\varphi \in {\mathcal {C}^{\varDelta }}(G-xy)$ is a coloring, $v\in V(G)$, and $\alpha \in \varphi (v)$, then there is a unique vertex $w\in N(v)$ such that $\varphi (vw)=\alpha$. We denote this vertex by $v_{\alpha ,\varphi }$, or by $v_{\alpha }$ if it is clear to which coloring we refer. By M(x, y) we denote the set of vertices $z\in N(y){\setminus }\{x\}$ for which there is a coloring $\varphi \in {\mathcal {C}^{\varDelta }}(G-xy)$ such that $\varphi (yz)\in \overline{\varphi }(x)$. Furthermore, we let $m(x,y)=|M(x,y)|$. If $z\in M(x,y)$, then $K=(x,xy,y,yz,z)$ forms a Kierstead path with respect to a certain coloring of ${\mathcal {C}^{\varDelta }}(G-xy)$, and so $d(x)+d(y)+d(z)\ge 2\varDelta +2$ (by Theorem 2.3). Furthermore, $N(z){\setminus }\{x,y\}$ contains at least $2\varDelta -d(x)-d(y)+1-\mu (z,x)$ vertices of maximum degree, provided that $\min \{d_G(y),d_G(z)\}<\varDelta$ (by Corollary 3.2). Hence we obtain the following adjacency lemma.

Lemma 3.1

Let G be a critical class two graph with maximum degree $\varDelta$. Then for every edge $xy\in E(G)$ there is a set of at least m(x, y) vertices $z\in N(y){\setminus }\{x\}$ such that $N(z){\setminus }\{x,y\}$ contains at least $2\varDelta -d(x)-d(y)+1-\mu (z,x)$ vertices of maximum degree, provided that $\min \{d_G(y),d_G(z)\}<\varDelta$.

To apply Lemma 3.1, we need lower bounds for the number m(x, y). To this end, let us fix a coloring $\varphi \in {\mathcal {C}^{\varDelta }}(G-xy)$. Now let $\varGamma$ denote the set of all colors $\gamma \in \{1,2, \ldots , \varDelta \}$ such that $\gamma \in \overline{\varphi }(x)$ or $d(x_{\gamma })+d(x)+d(y)< 2\varDelta +2$. Since G is a simple graph, we obtain $|\varGamma |=\varDelta -\sigma (y,x)$. If $\beta \in \overline{\varphi }(y)$, then $\beta \in \varphi (x)$ and $x_{\beta }\in M(y,x)$ implying that $d(y)+d(x)+d(x_{\beta })\ge 2\varDelta +2$. This shows that $\sigma (y,x)\ge |\overline{\varphi }(y)|=\varDelta -d(y)+1$ (by (1.1)). Clearly, $\sigma (y,x) \le |N(x)|-1\le d(x)-1$. Now, we claim that if $\gamma \in \varGamma$, then $y_{\gamma }$ exists and belongs to M(x, y), which implies that $M(x,y)=|\varGamma |$, and so

$$\begin{aligned} m(x,y)\ge \varDelta -\sigma (y,x)\ge \varDelta -d(x)+1. \end{aligned}$$

To prove the claim, let $\gamma \in \varGamma$. If $\gamma \in \overline{\varphi }(x)$, then $\gamma \in \varphi (y)$ and $y_{\gamma }\in M(x,y)$. Otherwise, $x_{\gamma }$ exists and we have (+) $d(x_{\gamma })+d(x)+d(y)<2\varDelta +2$. By (1.1), it follows that $|\overline{\varphi }(x_{\gamma })|=\varDelta -d(x_{\gamma })$ and $|\overline{\varphi }(x,y)|=2\varDelta +2-d(x)-d(y)$ as $\{x,y\}$ is $\varphi$-elementary and xy is uncolored. Then there is a color $\alpha \in \overline{\varphi }(x_{\gamma }) \cap \overline{\varphi }(x,y)$, for otherwise $|\overline{\varphi }(x_{\gamma },x,y)|=3\varDelta +2-(d(x_{\gamma })+d(x)+d(y))>\varDelta$ (by (+)), which is impossible. If $\alpha \in \overline{\varphi }(x_{\gamma })\cap \overline{\varphi }(x)$, then recoloring $xx_{\gamma }$ with $\alpha$ results in a coloring $\varphi '\in {\mathcal {C}^{\varDelta }}(G-xy)$ such that $\varphi '(yy_{\gamma })=\varphi (yy_{\gamma })=\gamma \in \overline{\varphi }'(x)$, and so $y_{\gamma }\in M(x,y)$ as claimed. If $\alpha \in \overline{\varphi }(x_{\gamma })\cap \overline{\varphi }(y)$, then there is a color $\beta \in \overline{\varphi }(x)$ and $\beta \not =\alpha$. Furthermore, $P_x(\alpha ,\beta ,\varphi )$ is a path joining x and y (by Theorem 2.1). Consequently, $\varphi '=\varphi /P_{x_{\gamma }}(\alpha ,\beta ,\varphi )\in {\mathcal {C}^{\varDelta }}(G-xy)$ satisfies $\varphi '(yy_{\gamma })=\varphi '(xx_{\gamma })=\gamma$ and $\beta \in \overline{\varphi }'(x_{\gamma })\cap \overline{\varphi }'(x)$. As in the former case, we can color $xx_{\gamma }$ with $\beta$ and then $\gamma$ is missing at x implying that $y_{\gamma }\in M(x,y)$. This completes the proof of the claim.

Now assume that q is an integer satisfying $\varDelta < 2q \le 2\varDelta -d(y)$. Let us fix a coloring $\varphi \in {\mathcal {C}^{\varDelta }}(G-xy)$. For $v\in V(G)$, let $\varphi (v,\ge q)=\left\{ \alpha \in \varphi (v) \;|\; d(v_\alpha )\ge q \right\}$ and $\varphi (v,<q)=\left\{ \alpha \in \varphi (v) \;|\; d(v_\alpha )<q \right\}$. Evidently, $\varphi (v)$ is the disjoint union of $\varphi (v,\ge q)$ and $\varphi (v,<q)$. Let us first show that $|\overline{\varphi }(y) \cap \varphi (x,<q)|\le 1$. For otherwise, $\overline{\varphi }(y) \cap \varphi (x,<q)$ contains two colors $\alpha , \beta$, and so $F=(x,xy,y,xx_\alpha ,x_\alpha ,xx_\beta ,x_\beta )$ is a $\varphi$-fan. Therefore, $\{y,x_\alpha ,x_\beta \}$ is $\varphi$-elementary and hence $|\overline{\varphi }(y,x_\alpha ,x_\beta )|>\varDelta +1-d(y)+2(\varDelta -q)\ge \varDelta +1,$ which is impossible. Clearly, $\sigma _q(y,x)=|\varphi (x,\ge q)|$ and $|\overline{\varphi }(x)|+|\varphi (x,<q)|=\varDelta -\sigma _q(y,x)$. Now let $\gamma$ and $\gamma '$ be two colors in $\varphi (y) \cap \varphi (x,<q)$. We claim that $y_\gamma$ or $y_{\gamma '}$ belongs to M(x, y). As $|\overline{\varphi }(y,x_\gamma ,x_{\gamma '})|>\varDelta$, one color, say $\alpha$, is missing at two vertices of $\{y,x_\gamma ,x_{\gamma '}\}$. First assume that $\alpha \in \overline{\varphi }(y)$. Then, by symmetry, $\alpha \in \overline{\varphi }(x_\gamma )$ and there is a color $\beta \in \overline{\varphi }(x)$. As xy is uncolored, $P=P_x(\alpha ,\beta ,\varphi )$ is a path between x and y. Hence $\varphi '=\varphi /P\in {\mathcal {C}^{\varDelta }}(g-xy)$ such that $\gamma =\varphi '(xx_g)=\varphi '(yy_\gamma )$ and $\beta \in \overline{\varphi }'(x_\gamma )\cap \overline{\varphi }'(x)$. If we color $xx_\gamma$ with $\beta$, then $\gamma$ is missing at x and so $y_\gamma \in M(x,y)$. It remains to consider the case that $\alpha \not \in \overline{\varphi }(y)$, and hence $\alpha \in \overline{\varphi }(x_\gamma )\cap \overline{\varphi }(x_{\gamma '})$. Then there is a color $\beta \in \overline{\varphi }(x)$. Then $x_\gamma$ or $x_{\gamma '}$ does not belong to $P=P_x(\alpha ,\beta ,\varphi )$, say $x_\gamma$ is not in P. Then $\varphi '=\varphi /P\in {\mathcal {C}^{\varDelta }}(G-xy)$ and recoloring $xx_\gamma$ with $\alpha$ results in a coloring $\varphi ''$ such that $\gamma =\varphi ''(yy_\gamma )$ is missing at x, and so $y_\gamma \in M(x,y)$. This proves the claim. As a consequence, we obtain that

$$\begin{aligned} m(x,y)\ge \varDelta -\sigma _q(y,x)-2. \end{aligned}$$

Using this and the fact that simple brooms are elementary, Cao et al. [13] proved the following counterparts to Woodall’s results, see Lemma 2.2.

Lemma 3.2

(Cao, Chen, Jiang, Liu, Lu) Let G be a critical class two graph with maximum degree $\varDelta$, let xy be a critical edge of G, and let q be an integer such that $\varDelta /2<q\le \varDelta +d(y)/2-4$. Then there are at least $\varDelta -\sigma _q(y,x)-2$ vertices $z \in N(y){\setminus }\{x\}$ such that $\sigma _q(y,z)+\sigma _q(y,x)\ge 2\varDelta -d(y)-4$.

Lemma 3.3

(Cao, Chen, Jiang, Liu, Lu) Let G be a critical class two graph with maximum degree $\varDelta$, let $x \in V(G)$, and let q be an integer such that $\varDelta /2<q\le \varDelta +d(y)/2-4$. Furthermore, let

$$\begin{aligned} p_{\mathrm {min}}=\min _{y\in N_G(x)}\sigma _q(x,y)-\varDelta +d(x)-1 \quad \text{ and } \quad p=\min \left\{ p_{\mathrm {min}}, \left\lfloor \frac{1}{2}d_G(x)\right\rfloor -3\right\} . \end{aligned}$$

Then x has at least $d(x)-p-1$ neighbors y for which $\sigma (x,y)\ge \varDelta -p-5$.

Lemma 3.3 is a key lemma in the proof of Cao et al. [13] showing that $a(\varDelta )\ge 0.69\varDelta$ for $\varDelta \ge 66$. As explained in the introduction of this section, if we want to show that $a(\varDelta )\ge q$ for $q>\tfrac{2}{3}(\varDelta +1)$, then a vertex v of small degree has to receive extra charge from vertices having distance 2 to v.

If xy is a critical edge of a class two graph with maximum degree $\varDelta$, then $d(x)+d(y)\ge \varDelta +2$ (by VAL) and Zhang [124] proved that equality implies that each vertex $z\in N(x,y){\setminus }\{x,y\}$ has degree $\varDelta$ and each vertex $u\in N(N(x,y)){\setminus }\{x,y\}$ satisfies $d(u)\ge \varDelta -1$ and $d(u)=\varDelta$, unless $(d(x),d(y))\in \{(\varDelta ,2),(2,\varDelta )\}$. A short proof of this result based on short Kierstead paths is given in [108, Theorem 4.30]. Recently, Cheng et al. [23] proved the following remarkable adjacency lemma. One step in the proof involves nine Kempe changes.

Lemma 3.4

(Cheng, Lorenzen, Luo, Thompson) Let G be a class two graph with maximum degree $\varDelta$ with $\varDelta \ge 4$, let xy be a critical edge of G such that $d(x)+d(y)=\varDelta +2$, $\min \{d(x),d(y)\}\ge 3$, and let z be a common neighbor of x and y. Then each vertex at distance at one or two from x or y has degree $\varDelta$, each vertex at distance three from x or y has degree at least $\varDelta -1$, and each vertex at distance two from z has degree $\varDelta$.

4 Concluding Remarks

In joint work with Wenan Zang, two of the authors of this survey, Guantao Chen and Guangming Jing gave a proof of Goldberg’s conjecture. They wrote the first draft of the paper in November 2017 and completed the second draft of the proof in March 2018. The current version of the paper is available at https://math.gsu.edu/gchen/research.html. The proof is based on an extension of Tashkinov’s method. Let us mention two interesting implications of Goldberg’s conjecture.

Theorem 4.1

If every graph satisfies $\chi '\le \max \{{\scriptstyle \mathcal {W}},\varDelta +1\}$, then the following statements hold:

• (a) If G is a graph with $\varDelta (G)=\varDelta$ and $\mu (G)=\mu$ such that $2p\mu +1 \le \varDelta \le 2(p+1)\mu -(2p+1)$ for some integer $p\ge 1$, then $\chi '(G)\le \varDelta +\mu -1$

• (b) Let G be a critical graph such that $\chi '(G)> \varDelta (G)+1+\frac{\varDelta (G)-2}{m-1}$ for an odd integer $m\ge 5$, then $|G|\le m-2$.

Statement (a) was proposed as a conjecture by Gupta [49] in his thesis; he also noticed that this would characterize exactly those values of $\varDelta$ and $\mu$ for which no graph G with $\varDelta (G)=\varDelta$, $\mu (G)=\mu$ and $\chi '(G)=\varDelta +\mu$ exist. That Gupta’s conjecture is implied by Goldberg’s conjecture was proved by Scheide and Stiebitz [100] (see also [108, Sect. 7.2]). Statement (b) was proposed as a conjecture by Jakobsen [61] at the graph theory conference in Keszthely (Hungary) in 1973 and published in 1975 in the proceedings of the conference; that Jakobsen’s conjecture is implied by Goldberg’s conjecture follows from Lemma 1.2 and (1.1) (see also [108, Sect. 6.1]). Theorem 1.2(a) imply statement (a) for $1 \le p \le 18$ (see the proof of Theorem 7.11 in [108]) and statement (b) for $m\le 39$.

In this survey we mainly focused on new results related to Goldberg’s conjecture and to the Classification Problem for simple graphs. Two topics which we did not consider in this survey, but which received a lot of attention in the recent years, are list edge colorings and acyclic edge colorings of graphs. The question of when a k-edge-coloring of a subgraph of a graph can be extended to a k-edge-coloring of the whole graph, was first studied in 1990 by Marcotte and Seymour [75]. However, the edge-precolouring extension problem has been less comprehensively studied than its vertex-colouring counterpart. In a recent paper by Edwards et al. [36], precolouring extension problems for proper edge-colourings of graphs are considered, in an attempt to prove stronger versions of Vizings and Shannons bounds on the chromatic index of graphs in terms of their maximum degree. Two other recent papers devoted to the edge-precolouring extension problem are the papers by Harrelson et al. [51] and by Girão and Kang [43]. In the latter paper, the authors prove that if G is a graph with $\varDelta (G)=\varDelta$ and $\mu (G)=\mu$, then any precoloring of a set of edges having pairwise distance at least 9 with $\varDelta +\mu$ colors can be extended to a $(\varDelta +\mu )$-edge-coloring of G. In a short note from 2014 Kostochka [68] presents an auxiliary multi-digraph that simplifies and facilitates the proof of the Vizing-Gupta bound and VAL.