TOPICS

# 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).

Class 1 Graph, Petersen Graph, Snark, Vizing's Theorem

Portions 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

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

Class 2 Graph

## Cite this as:

Pegg, Ed Jr.; Wagon, Stan; and Weisstein, Eric W. "Class 2 Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Class2Graph.html