Class 1 Graph
Vizing's theorem states that a graph can be edge-colored in either Delta or Delta+1 colors, where Delta is the maximum vertex degree of the graph. A graph with edge chromatic number equal to Delta 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 Delta>7 (Cole and Kowalik 2008).
Class 1 graphs have both edge chromatic number and fractional edge chromatic number equal to Delta.
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 n=1, 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).
See also
Class 2 Graph, Edge Chromatic Number, König's Line Coloring Theorem, Vizing's TheoremPortions of this entry contributed by Ed Pegg, Jr. (author's link)
Portions of this entry contributed by Stan Wagon
Explore with Wolfram|Alpha
More things to try:
References
Aubert, J. and Schneider, B. "Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens." Disc. Math. 38, 7-16, 1982.Cole, R. and Kowalik, L. "New Linear-Time Algorithms for Edge-Coloring Planar Graphs." Algorithmica 50, 351-368, 2008.Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." 25 Jun 2016. https://arxiv.org/abs/1606.07918.Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.Sloane, N. J. A. Sequences A099435 and A099436 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Class 1 GraphCite this as:
Pegg, Ed Jr.; Wagon, Stan; and Weisstein, Eric W. "Class 1 Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Class1Graph.html