Liczba chromatyczna

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

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.:

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

Zobacz też

• indeks chromatyczny
• kolorowanie grafu