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.
Sformułowanie twierdzenia
Każdy nieskierowany graf prosty 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, czyli stopniowi równemu: .
Uwaga. Powyższe twierdzenie, można zapisać także jako następujący ciąg nierówności, dla grafu określonego jak powyżej:
Klasy grafów
Definicja. Grafy, które można pokolorować krawędziowo przy pomocy kolorów, należą do tak zwanej klasy pierwszej (ang. „class one” graphs).
Z kolei grafy, które można pokolorować za pomocą kolorów, należą do tak zwanej klasy drugiej (ang. „class two” graphs).
Przypisy
Vizinga