Class 1 Graph

A class 1 graph is a simple graph whose edge chromatic number equals its maximum vertex degree . Vizing's theorem states that a simple graph can be edge-colored in either or colors.

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 graphs, and windmill graphs (S. Wagon, pers. comm., Oct. 27-28, 2011). Keller graphs are class 1 (Jarnicki et al. 2016). For positive integers and , rook graphs are class 1 when is even, and class 2 when is odd and greater than 1. The singleton graph is class 1.

The numbers of nonisomorphic class 1 simple graphs on , 2, ... vertices are 1, 2, 3, 10, 28, 145, ... (OEIS A099435).

Similarly, the numbers of nonisomorphic connected class 1 simple graphs are 1, 1, 1, 6, 17, 109, 821, 11050, 260150, ... (OEIS A099436; Royle).