Twierdzenie Vizinga

Twierdzenie Vizinga – twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i indeksem chromatycznym w grafie.

Nazwa twierdzenia została ustanowiona na cześć ukraińskiego matematyka Vadima Georgievicha Vizinga, który opublikował jego pełen dowód w roku 1964^[1].

Każdy nieskierowany graf prosty ${\displaystyle G}$ można pokolorować krawędziowo używając liczby kolorów równej maksymalnemu stopniowi wierzchołka ${\displaystyle \Delta }$, lub maksymalnemu stopniowi wierzchołka powiększonemu o jeden, czyli stopniowi równemu: ${\displaystyle \Delta +1}$^[2].

Uwaga. Powyższe twierdzenie, można zapisać także jako następujący ciąg nierówności, dla grafu ${\displaystyle G}$ określonego jak powyżej:

${\displaystyle \Delta (G)\leqslant \chi '(G)\leqslant \Delta (G)+1}$

Definicja. Grafy, które można pokolorować krawędziowo przy pomocy ${\displaystyle \Delta }$ kolorów, należą do tak zwanej klasy pierwszej (ang. „class one” graphs).

Z kolei grafy, które można pokolorować za pomocą ${\displaystyle \Delta +1}$ kolorów, należą do tak zwanej klasy drugiej (ang. „class two” graphs).