Indeks chromatyczny grafu, ozn. – pojęcie związane z kolorowaniem krawędzi grafu. Określa ono minimalną liczbę kolorów, wystarczającą do prawidłowego pokolorowania krawędzi grafu.
Innymi słowy, indeks chromatyczny grafu, jest to najmniejsza liczba kolorów potrzebnych do pomalowania krawędzi tak, aby żadne dwie krawędzie mające wspólny wierzchołek nie były tego samego koloru (to jest właśnie warunek z definicji prawidłowego kolorowania krawędzi).
Właściwości indeksu chromatycznego
Indeks chromatyczny grafu jest równy liczbie chromatycznej jego grafu krawędziowego.
Znalezienie indeksu chromatycznego jest problemem NP-trudnym, mimo że można bardzo dokładnie oszacować jego wartość.
Twierdzenie Vizinga. Vadim G. Vizing udowodnił w 1964, że . Ponieważ jednocześnie ; więc jeśli znamy stopień grafu, to jesteśmy w stanie także powiedzieć, że indeks chromatyczny przyjmuje dokładnie jedną z dwóch wartości: , oraz . Por. (artykuł): Twierdzenie Vizinga.
Klasy grafów
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