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?



Class 1 vs. class 2 in regular graphs
In [a series of four papers](http://arxiv.org/find/all/1/all:+1-factorization/0/1/0/all/0/1) 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](http://www.math.uiuc.edu/%7Ewest/openp/overfull.html) 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**](http://dx.doi.org/10.1016/0095-8956(85)90056-5), J. Comb. Theory, Ser. B 39, 298-307 (1985). [ZBL0581.05031](https://zbmath.org/?q=an:0581.05031).


