Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba taka, że możliwe jest legalne pokolorowanie wierzchołków grafu Oznacza się ją symbolem .
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.: gdzie jest rozmiarem maksymalnej kliki grafu Twierdzenie Brooksa: dla grafów pełnych oraz cykli o nieparzystej długości gdzie jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów spójnych zachodzi , dla grafów planarnych dla drzew o co najmniej dwóch wierzchołkach
Zobacz też indeks chromatyczny kolorowanie grafu
Przypisy
Linki zewnętrzne
[dostęp 2025-10-12].
Kategoria:Teoria grafów