Class 2 Graph

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 2 graph.

Class 2 graphs include the Petersen graph, complete graphs  for , 5, 7, ..., and the snarks.

All non-empty regular graphs with an odd number of nodes  are class 2 by parity. Such graphs automatically have an even number of edges per vertex.

A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph  is trivially class 2 if

where  is the matching number,  the maximum vertex degree, and  the edge count of .

The following table summarizes some named class 2 graphs.

graph
triangle graph	3
pentatope graph	5
Petersen graph	10
first Blanuša snark	18
second Blanuša snark	18
Robertson graph	19
flower snark	20
25-Grünbaum graph	25
Doyle graph	27
double star snark	30
Szekeres snark	50
McLaughlin graph	275

The numbers of simple class 2 graphs on , 2, ... nodes are 0, 0, 1, 1, 6, 11, 50, 131, 1131, ... (OEIS A099437).

Similarly, the numbers of simple connected class 2 graphs are 0, 0, 1, 0, 4, 3, 32, 67, 930, ... (OEIS A099438; Royle).

REFERENCES

Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.

Sloane, N. J. A. Sequences A099437 and A099438 in "The On-Line Encyclopedia of Integer Sequences."