Vizing's theorem states that a graph can be edge-colored in either 
or 
colors, where 
is the maximum vertex
degree of the graph. A graph with edge chromatic
number equal to 
is known as a class 1 graph.
König's line coloring theorem states that all bipartite graphs are class 1.
All cubic Hamiltonian
graphs are class 1, as are planar graphs with
maximum vertex degree 
(Cole and Kowalik 2008).
Class 1 graphs have both edge chromatic number and fractional edge chromatic number
equal to 
.
Families of non-bipartite graphs that appear to be class 1 (or at least whose smallest members are all class 1) include king, Lindgren-Sousselier, and windmill graphs (S. Wagon, pers. comm., Oct. 27-28, 2011). Keller graphs are class 1 (Jarnicki et al. 2015). Aubert and Schneider (1982) showed that rook graphs admit Hamiltonian decomposition, meaning they are class 1 when they have even vertex count and class 2 when they have odd vertex count (because they are odd regular).
The numbers of simple class 1 graphs on 
, 2, ... nodes are 1, 2, 3, 10, 28, 145, ... (OEIS A099435).
Similarly, the numbers of simple connected class 1 graphs are 1, 1, 1, 6, 17, 109, 821, 11050, 260150, ... (OEIS A099436; Royle).
