[Math] Class 1 vs. class 2 in regular graphs

Question

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph.

A graph with edge chromatic number equal to $\Delta$ is known as a class 1 graph.

A graph with edge chromatic number equal to $\Delta+1$ is known as a class 2 graph.

If we consider only regular graphs, which one of them are bigger in the class of regular graphs (contains more graphs), and why?

Answer 1

In a series of four papers recently posted on the arXiv, Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown show that every large $D$-regular even graph with $D \geq 2\lceil n/4\rceil -1$ can be covered by edge-disjoint matchings, i.e. is class 1.

In a sequence of four papers, we prove the following results (via a unified approach) for all sufficiently large $n$:

(i) [1-factorization conjecture] Suppose that $n$ is even and $D \geq 2\lceil n/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.

(ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor $. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into Hamilton cycles and at most one perfect matching.

(iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on $n$ vertices with minimum degree $\delta\ge n/2$. Then $G$ contains at least ${\rm reg}_{\rm even}(n,\delta)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here ${\rm reg}_{\rm even}(n,\delta)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $\delta$. According to Dirac, (i) was first raised in the 1950s. (ii) and the special case $\delta= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible. In the current paper, we prove the above results for the case when $G$ is close to the union of two disjoint cliques.

For (not necessarily regular) graphs of maximum degree down to $n/3$ the overfull conjecture is that the only obstruction to being class 1 is an odd order subgraph $H$ with more than $\Delta(G)(|H|-1)$ edges (too many to $\Delta$-colour).

---

Added by later editors:

There is also an old result by Richard Stong regarding 1-factorizability of even Cayley graphs:

Stong, Richard A., On 1-factorizability of Cayley graphs, J. Comb. Theory, Ser. B 39, 298-307 (1985). ZBL0581.05031.