Satz von Vizing
# 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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): G ein Multigraph, d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index $\chi ^{\prime }(G)$ und dem Maximalgrad $\Delta (G)$. Weiterhin bezeichne $h$ die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

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

Diese Ungleichung ist optimal, die Gleichung $\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:

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