Twierdzenie Vizinga

Twierdzenie Vizingatwierdzenie 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 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[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.

PrzypisyEdytuj

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 103-105. ISBN 0-387-95014-1.