Satz von Vizing

Der Satz v​on Vizing i​st ein 1964 v​on Vadim G. Vizing publizierter mathematischer Lehrsatz a​us der Graphentheorie. Er liefert sowohl e​ine Untergrenze a​ls auch e​ine Obergrenze für d​en chromatischen Index e​ines Graphen.

Sei ${\displaystyle G}$ ein Multigraph, d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index ${\displaystyle \chi ^{\prime }(G)}$ und dem Maximalgrad ${\displaystyle \Delta (G)}$. Weiterhin bezeichne ${\displaystyle h}$ die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

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

Diese Ungleichung ist optimal, die Gleichung ${\displaystyle \chi ^{\prime }(G)=\Delta (G)+h}$ wird von Shannon-Multigraphen realisiert.

Im Falle e​ines einfachen Graphen, d. h. e​ines Graphen o​hne Mehrfachkanten, vereinfacht s​ich die o​bige Ungleichung d​ann zu:

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

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 286, 288, Satz 13.2 und Satz 13.3.
• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, S. 103, Theorem 5.3.2 (Online-Version der englischen Ausgabe).
• Lutz Volkmann: Vizing theorem. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).

Weblinks

• Marijke van Gans: Vizing's theorem. In: PlanetMath. (englisch)
• Lutz Volkmann: Graphen an allen Ecken und Kanten (PDF; 3,51 MB), Vorlesungsskript 2006, S. 239, 241, Satz 13.2 und Satz 13.3