Vizing's theorem
The set of Vizing is a 1964 by Vadim G. Vizing published mathematical theorem from graph theory . It provides both a lower limit and an upper limit for the chromatic index of a graph.
Be a multigraph , i. H. a graph with multiple edges but without loops, with the chromatic index and the maximum degree . Also denote the maximum number of edges that connect two corners. Then the following inequality applies:
This inequality is optimal, the equation is realized by Shannon multigraphs .
In the case of a simple graph , i.e. H. of a graph without multiple edges, the above inequality then simplifies to:
literature
- Lutz Volkmann: Fundamente der Graphentheorie , Springer (Vienna) 1996, ISBN 3-211-82774-9 , pp. 286, 288, sentence 13.2 and sentence 13.3.
- Reinhard Diestel: graph theory . Springer 2006, ISBN 3-540-21391-0 , p. 103, Theorem 5.3.2 ( online version of the English edition ).
- Lutz Volkmann: Vizing theorem . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
Web links
- Marijke van Gans: Vizing's theorem . In: PlanetMath . (English)
- Lutz Volkmann: Graphs on all corners and edges (PDF; 3.51 MB) , lecture script 2006, pp. 239, 241, sentence 13.2 and sentence 13.3