TOPICS
Search

Vizing's Theorem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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. This partitions graphs into two classes, with the ones requiring Delta colors known as class 1, and the ones requiring Delta+1 colors known as class 2 graphs.

See also

Brooks' Theorem, Class 1 Graph, Class 2 Graph, Degree Sequence, Edge Chromatic Number, Snark, Vertex Degree, Vizing Conjecture

Explore 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 Theorem

Cite this as:

Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VizingsTheorem.html

Subject classifications