Konsekwencją powyższego twierdzenia Vizinga, jest także podział wszystkich grafów na dwie klasy ze względu na indeks chromatyczny. Okazuje się, że znacznie więcej jest grafów o indeksie chromatycznym równym dokładnie . Grafy takie nazywamy grafami klasy 1 (ang. „class one” graphs), a ich przykładami są grafy dwudzielne, a także grafy pełne o parzystej liczbie wierzchołków.
Z kolei do grafów tak zwanej klasy 2 (ang. „class two” graphs) – którymi chcemy nazywać grafy o indeksie chromatycznym równym – należy zaliczyć np. nieparzyste cykle; jak również grafy pełne nieparzystego rzędu.
Cykle
Można udowodnić, że indeks chromatyczny dowolnego nieparzystego cyklu wynosi 3.
Zobacz też Graf krawędziowy Kolorowanie krawędzi Liczba chromatyczna Problemy NP-trudne
Przypisy
Linki zewnętrzne [dostęp 2025-12-20].
Kategoria:Teoria grafów