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: ${\displaystyle G}$ ${\displaystyle \chi ^{\prime }(G)}$ ${\displaystyle \Delta (G)}$ ${\displaystyle h}$

${\displaystyle \Delta (G)\leq \chi ^{\prime }(G)\leq \Delta (G)+h.}$

This inequality is optimal, the equation is realized by Shannon multigraphs . ${\displaystyle \chi ^{\prime }(G)=\Delta (G)+h}$

In the case of a simple graph , i.e. H. of a graph without multiple edges, the above inequality then simplifies to:

${\displaystyle \Delta (G)\leq \chi ^{\prime }(G)\leq \Delta (G)+1}$

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