Liczba multichromatyczna (inaczej: ważona liczba chromatyczna) – najmniejsza liczba kolorów (najmniejsza moc zbioru kolorów ) niezbędna do legalnego pokolorowania grafu ważonego Rafał Witkowski: Multikolorowanie grafów, X Międzynarodowe Warsztaty Młodych Matematyków, s. 206–218, 2007.. Oznacza się ją w różny sposób, między innymi przez przy czym indeksy i bywają zamieniane na inne lub, jeżeli fakt, iż chodzi o liczbę multichromatyczną grafu ważonego wynika z kontekstu – są pomijane.
Jeżeli wszystkie wagi wierzchołków w grafie są równe 1, wtedy liczba multichromatyczna jest liczbą chromatyczną tego grafu.
Wartość dla dowolnego grafu Oszacowanie z dołu gdzie oznacza ważoną liczbę klikową grafu (tj. największą wagę kliki spośród wszystkich klik w ). Nierówność ta jest prawdziwa dla każdego grafu, gdyż w każdej klice do multikolorowania trzeba użyć co najmniej tylu kolorów, ile wynosi suma wag jej wierzchołkówRafał Witkowski: Algorytmy multikolorowania grafów w modelu rozproszonym, Zakład Matematyki Dyskretnej Uniwersytetu im. Adama Mickiewicza, 2010..
Oszacowanie z góry Mimo istnienia prac na temat multikolorowania szczególnych rodzajów grafów, nie są znane dobre oszacowania liczby multichromatycznej z góry w przypadku ogólnym.
Wykorzystując wartość zwykłej liczby chromatycznej i wiedząc, że graf -kolorowalny w sensie zwykłym, da się podzielić na zbiorów niezależnych, można oszacować liczbę multichromatyczną z góry przez -krotność wagi najcięższego wierzchołka w grafie. W danym zbiorze niezależnym można legalnie pokolorować wierzchołki stosując dla każdego te same kolory; potrzeba do tego najwyżej tyle barw, ile wynosi waga najcięższego wierzchołka w grafie Podobnie postępujemy dla każdego z zbiorów niezależnych, kolorując je na różne zestawy kolorów. Stąd .
Powyższe oszacowanie ulepsza się na dwa sposoby. Pierwszym jest zastąpienie największej wagi w całym grafie największymi wagami wierzchołków w poszczególnych zbiorach niezależnych (oznaczanych gdzie ). Stąd oszacowanie
Drugi sposób wykorzystuje twierdzenie Brooksa (mówiące, że dla każdego grafu prostego zachodzi ). Zastępując jego oszacowaniem, otrzymuje się następujące oszacowanie liczby multichromatycznej: .
Nie są znane inne oszacowania w przypadku ogólnym.
Wartość dla szczególnych klas grafów Dla grafów dwudzielnych i doskonałych Dla grafów dwudzielnych znana jest dokładna wartość liczby multichromatycznej. Dla każdego ważonego grafu dwudzielnego zachodzi równość Lata Narayanan, Sunil. M. Shende: Static frequency assignment in cellular networks, Algorithmica 29, s. 396–409, 2001..
Powyższa równość jest prawdziwa także dla grafów doskonałychRichard Diestel: Graph theory II, Springer-Verlag, 2000..
Dla cykli Dla każdego ważonego cyklu o wierzchołkach z funkcją wagi zachodzi równość: .
Dla grafów planarnych Dla każdego grafu planarnego zachodzi nierówność Togni: Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes, Discrete mathematics & theoretical computer science 8(1), s. 159–172, 2006..
Zobacz też kolorowanie grafu liczba chromatyczna multikolorowanie grafu
Przypisy
Kategoria:Teoria grafów