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 G ein Multigraph, d.h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index $\chi^{\prime}(G)$ und dem maximalen Grad Δ(G). Weiterhin bezeichne h die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

$\Delta(G)\le\chi^{\prime}(G)\le\Delta(G)+h$

Im Falle eine schlichten Graphen, d.h. eines Graphen ohne Mehrfachkanten, vereinfacht sich die obige Ungleichung dann zu:

$\Delta(G)\le\chi^{\prime}(G)\le\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 (elektronische Online-Version)
• Vizing theorem in der Encyclopaedia of Mathematics

Weblinks

• Vizing's Theorem auf PlanetMath
• Lutz Volkmann: Graphen an allen Ecken und Kanten, Vorlesungsskript 2006, S. 239, 241, Satz 13.2 und Satz 13.3