Twierdzenie Vizinga


Twierdzenie Vizinga w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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].

Δ ( G ) χ ( G ) Δ ( G ) + 1 {\displaystyle \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.

Przypisy | edytuj kod

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 103-105. ISBN 0-387-95014-1.
Na podstawie artykułu: "Twierdzenie Vizinga" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy