Liczba chromatyczna
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 [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.:
- 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 [2],
- dla grafów planarnych
- dla drzew o co najmniej dwóch wierzchołkach
Zobacz też
- indeks chromatyczny
- kolorowanie grafu
Przypisy
Linki zewnętrzne
- MichałM. Adamaszek MichałM., Liczba chromatyczna płaszczyzny, „Delta”, lipiec 2008, ISSN 0137-3005 [dostęp 2022-07-20] .
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |