Satz von Vizing

Der Satz von Vizing ist ein 1964 von Vadim G. Vizing publizierter mathematischer Lehrsatz aus der Graphentheorie. Er liefert sowohl eine Untergrenze als auch eine Obergrenze für den chromatischen Index eines 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 eines einfachen Graphen, d. h. eines Graphen ohne Mehrfachkanten, vereinfacht sich die obige Ungleichung dann 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 1-55608-010-7 (englisch, encyclopediaofmath.org).

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