Indeks chromatyczny
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Indeks chromatyczny grafu (χ'(G)) jest pojęciem związanym z kolorowaniem krawędzi grafu. Określa minimalną liczbę kolorów wystarczającą do prawidłowego pokolorowania krawędzi grafu.
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ść. V. G. Vizing udowodnił, że 
. Ponieważ oczywiste jest, że 
, więc jeśli znamy stopień grafu wiemy, że indeks chromatyczny przyjmuje jedną z dwóch wartości: 
, 
.
Stało się to pretekstem do podziału 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 . Grafy takie nazywamy grafami klasy 1, a ich przykładami są grafy dwudzielne, a także grafy pełne o parzystej liczbie wierzchołków. Grafami klasy 2, a więc o indeksie chromatycznym równym , są np. nieparzyste cykle, jak również grafy pełne nieparzystego rzędu.
