Wolna encyklopedia
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Liczba chromatyczna - w teorii grafów jest to liczba kolorów (liczb) 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 k kolorami. Oznacza się ją symbolem χ(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.:
, gdzie ω jest rozmiarem maksymalnej kliki grafu G- dla grafów pełnych oraz cykli o nieparzystej długości χ(G) = Δ + 1, gdzie Δ jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów zachodzi
- dla grafów planarnych
- dla drzew o co najmniej dwóch wierzchołkach χ(G) = 2