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

Przypisy

1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 95. ISBN 0-387-95014-1.
2. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 99. ISBN 0-387-95014-1.

Linki zewnętrzne

• MichałM. Adamaszek MichałM., Liczba chromatyczna płaszczyzny, „Delta”, lipiec 2008, ISSN 0137-3005 [dostęp 2022-07-20].
• JoannaJ. Jaszuńska JoannaJ., Kolorowa płaszczyzna, „Delta”, grudzień 2018, ISSN 0137-3005 [dostęp 2024-10-30].