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.

$\mathrm{\Delta }(G)⩽{\chi }^{\prime }(G)⩽\mathrm{\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.