Vizing's theorem states that a graph can be edge-colored in either Δ or Δ + 1 colors, where Δ is the maximum vertex degree of the graph. A graph with edge chromatic number equal to Δ is known as a class 1 graph. König's line coloring theorem states that all bipartite graphs are class 1. All cubic Hamiltonian graphs are class 1, as are planar graphs with maximum vertex degree Δ>7. Class 1 graphs have both edge chromatic number and fractional edge chromatic number equal to Δ.

class 2 graph | edge chromatic number | König's line coloring theorem | Vizing's theorem