Class 2 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+1 is known as a class 2 graph.

Class 2 graphs include the Petersen graph, complete graphs K_n for n=3, 5, 7, ..., and the snarks.

All non-empty regular graphs with an odd number of nodes n>1 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 G is trivially class 2 if

where nu(G) is the matching number, Delta(G) the maximum vertex degree, and m the edge count of G.

The following table summarizes some named class 2 graphs.

The numbers of simple class 2 graphs on n=1, 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).

See also

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Portions of this entry contributed by Stan Wagon

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

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

Subject classifications