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)\geqslant 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)\leqslant 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)\leqslant \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)\leqslant \Delta (G)+1$). Zastępując $k$ jego oszacowaniem, otrzymuje się następujące oszacowanie liczby multichromatycznej: $\chi _{m}(G)\leqslant (\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{cases}W(C_{k})&{\text{dla }}k=2m\\max\left\{W(C_{k}),\left\lceil {\frac {1}{m}}\sum _{i=1}^{k}\omega (v_{i})\right\rceil \right\}&{\text{dla }}k=2m+1\end{cases}}$.

Dla grafów planarnych

Dla każdego grafu planarnego $G$ zachodzi nierówność $\chi _{m}(G)\leqslant \left\lceil {\frac {11}{6}}W(G)\right\rceil$.

Zobacz też

• kolorowanie grafu
• liczba chromatyczna
• multikolorowanie grafu