Liczba chromatyczna

Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba $k$ taka, że możliwe jest legalne pokolorowanie wierzchołków grafu $G.$ Oznacza się ją symbolem $\chi (G)$.

Problem wyznaczenia liczby chromatycznej jest NP-trudny – nie są znane niezawodne wielomianowe algorytmy wyznaczające liczbę chromatyczną każdego grafu. Istnieje jednak szereg oszacowań liczby chromatycznej dla różnych klas grafów, np.:

• $\chi (G)⩾\omega ,$ gdzie $\omega$ jest rozmiarem maksymalnej kliki grafu $G,$
• Twierdzenie Brooksa: dla grafów pełnych oraz cykli o nieparzystej długości $\chi (G)=\mathrm{\Delta }+1,$ gdzie $\mathrm{\Delta }$ jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów spójnych zachodzi $\chi (G)⩽\mathrm{\Delta }$,
• dla grafów planarnych $\chi (G)⩽4,$
• dla drzew o co najmniej dwóch wierzchołkach $\chi (G)=2.$

Zobacz też

• indeks chromatyczny
• kolorowanie grafu

Linki zewnętrzne

• Szablon:Pismo Delta
• Szablon:Pismo Delta