TOPICS
Search

König's Line Coloring Theorem


König's line coloring theorem states that the edge chromatic number of any bipartite graph equals its maximum vertex degree. In other words, every bipartite graph is a class 1 graph.


See also

Bipartite Graph, Edge Chromatic Number, König-Egeváry Theorem, König's Theorem

Explore with Wolfram|Alpha

References

Biggs, N. L.; Lloyd, E. K.; and Wilson, R. J. Graph Theory 1736-1936. Oxford University Press, pp. 203-207, 1976.Kőnig, D. "Gráfok és alkalmazásuk a determinánsok Žs a halmazok elméletére." Matematikai és Természettudományi Értesítő 34, 104-119, 1916.Lovász, L. and Plummer, M. D. Matching Theory. New York: North-Holland, p. 37, 1986.

Cite this as:

Weisstein, Eric W. "König's Line Coloring Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KoenigsLineColoringTheorem.html

Subject classifications