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)\geqslant \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)=\Delta +1,$ gdzie $\Delta$ jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów spójnych zachodzi $\chi (G)\leqslant \Delta$,
• dla grafów planarnych $\chi (G)\leqslant 4,$
• dla drzew o co najmniej dwóch wierzchołkach $\chi (G)=2.$

Zobacz też

• indeks chromatyczny
• kolorowanie grafu

Linki zewnętrzne

• MichałM. Adamaszek MichałM., Liczba chromatyczna płaszczyzny, [w:] pismo „Delta”, deltami.edu.pl, lipiec 2008, ISSN 0137-3005 [dostęp 2022-07-20]  (pol.).