Indeksem chromatyczny grafu nazywamy wielkość, określającą minimalną liczba kolorów wystarczająca do pokolorowania krawędzi tegoż grafu, w sposób prawidłowy (według definicji prawidłowego kolorowania powyżej). Indeks chromatyczny dla danego grafu , oznaczamy przy wykorzystaniu symbolu: .
Kolorowanie krawędzi jest równoważne kolorowaniu wierzchołków tak zwanego grafu krawędziowego.
Najmniejsza liczba kolorów
Niech dalej, oznacza zbiór kolorów krawędzi incydentnych z danym wierzchołkiem .
Kolorowanie krawędzi grafu nazywamy kolorowaniem krawędzi rozróżniającym wierzchołki, jeśli dla każdej pary wierzchołków i zbiory , są różne. Niech będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania (krawędziowego), jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast będzie najmniejszą liczbą kolorów potrzebnych do niewłaściwego kolorowania rozróżniającego wierzchołki.
P.N. Balister, B. Bollobás oraz R.H. Schelp udowodnili następujące twierdzenie:
Twierdzenie. Niech graf będzie grafem dwuregularnym, wówczas .