Indeksem chromatycznym grafu nazywamy najmniejszą liczbę kolorów, którymi można pokolorować krawędzie grafu w taki sposób, aby każde dwie krawędzie o wspólnym końcu miały różne kolory.

Indeks chromatyczny grafu $G$ oznaczamy $\chi'(G)$.

W 1964 roku Vizing udowodnił, że:

$\Delta(G)$ $\leq$ $\chi'(G)$ $\leq$ $\Delta(G)$ $+ 1$.

??? Znajdź indeks chromatyczny poniższego grafu.

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej