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."
