Liczba multichromatyczna

Liczba multichromatyczna (inaczej: ważona liczba chromatyczna) – najmniejsza liczba kolorów (najmniejsza moc zbioru kolorów $C$) niezbędna do legalnego pokolorowania grafu ważonego $G_{\omega }$. Oznacza się ją w różny sposób, między innymi przez ${\chi }_m(G_{\omega }),$ przy czym indeksy $m$ i $\omega$ 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

${\chi }_m(G)⩾W(G),$ gdzie $W(G)$ oznacza ważoną liczbę klikową grafu $G$ (tj. największą wagę kliki spośród wszystkich klik w $G$). 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ów.

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 $k$-kolorowalny w sensie zwykłym, da się podzielić na $k$ zbiorów niezależnych, można oszacować liczbę multichromatyczną z góry przez $k$-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 $G.$ Podobnie postępujemy dla każdego z $k$ zbiorów niezależnych, kolorując je na różne zestawy kolorów. Stąd ${\chi }_m(G)⩽k\cdot max\{\omega (v):v\in V(G)\}$.

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 $V_i(G),$ gdzie $i=\{1,...,k\}$). Stąd oszacowanie ${\chi }_m(G)⩽\sum _{i=1}^{k}max\{\omega (v):v\in V_i(G)\}.$

Drugi sposób wykorzystuje twierdzenie Brooks’a (mówiące, że dla każdego grafu prostego zachodzi $\chi (G)⩽\mathrm{\Delta }(G)+1$). Zastępując $k$ jego oszacowaniem, otrzymuje się następujące oszacowanie liczby multichromatycznej: ${\chi }_m(G)⩽(\mathrm{\Delta }(G)+1)max\{\omega (v):v\in V(G)\}$.

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 $G$ zachodzi równość ${\chi }_m(G)=W(G)$.

Powyższa równość jest prawdziwa także dla grafów doskonałych.

Dla cykli

Dla każdego ważonego cyklu $C_k$ o wierzchołkach $v_1,v_2,\dots ,v_k$ z funkcją wagi $\omega$ zachodzi równość: ${\chi }_m(C_k)=\{\begin{array}{cc}W(C_k)& \text{dla }k=2m\\ max\{W(C_k),\lceil \frac{1}{m}\sum _{i=1}^k\omega (v_i)\rceil \}& \text{dla }k=2m+1\end{array}$.

Dla grafów planarnych

Dla każdego grafu planarnego $G$ zachodzi nierówność ${\chi }_m(G)⩽\lceil \frac{11}{6}W(G)\rceil$.

Zobacz też

• kolorowanie grafu
• liczba chromatyczna
• multikolorowanie grafu