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