Let be the maximum degree of the graph, then a graph with edge chromatic number equal to is known as a class 1 graph.

All cubic Hamiltonian graphs are class 1.

The numbers of simple class 1 graphs on , 2, ... nodes are 1, 2, 3, 10, 28, 145, ... (Sloane's A099435).

Similarly, the numbers of simple connected class 1 graphs are 1, 1, 1, 6, 17, 109, ... (Sloane's A099436).

This entry contributed by Ed Pegg, Jr. (author's link)

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

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

CITE THIS AS:

Pegg, Ed Jr. "Class 1 Graph." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/Class1Graph.html