Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. This partitions graphs into two classes, with the ones requiring colors known as class 1, and the ones requiring colors known as class 2 graphs.
Vizing's Theorem
See also
Brooks' Theorem, Class 1 Graph, Class 2 Graph, Degree Sequence, Edge Chromatic Number, Snark, Vertex Degree, Vizing ConjectureExplore with Wolfram|Alpha
References
Misra, J. and Gries, D. "A Constructive Proof of Vizing's Theorem." Inform. Process. Lett. 41, 131-133, 1992.Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, p. 77, 2011.Referenced on Wolfram|Alpha
Vizing's TheoremCite this as:
Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VizingsTheorem.html