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ł je w 1964 roku.

Każdy nieskierowany graf prosty G można pokolorować krawędziowo używając liczby kolorów równej maksymalnemu stopniowi wierzchołka Δ, lub maksymalnemu stopniowi wierzchołka powiększonemu o jeden Δ+ 1.

$\Delta (G)\leqslant \chi '(G)\leqslant \Delta (G)+1$

Grafy, które można pokolorować krawędziowo przy pomocy Δ kolorów, należą do klasy 1., a grafy, które można pokolorować za pomocą Δ+1 kolorów, należą do klasy 2.