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}$