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
oznaczamy
.
W 1964 roku Vizing udowodnił, że:
??? Znajdź indeks chromatyczny poniższego grafu.
![]()
![]()
![]()
![]()
![]()
.
![]()
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej