Kolorowanie grafów

Kolorowanie wierzchołków grafu

Kolorowanie wierzchołków polega na kolorowaniu w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały takiego samego koloru. Ogólnie mówimy, że dany graf bez pętli $G$ jest $k$-kolorowalny$(v)$ jeśli wierzchołki mogą być podzielone na takie zbiory: $V_1,V_2,\ldots,V_k$, aby żadne dwa wierzchołki sąsiednie nie należały do tego samego zbioru. Jeśli graf $G$ jest $k$-kolorowalny$(v)$, lecz nie jest już $(k-1)$-kolorowalny$(v)$ mówimy, że jest $k$-chromatyczny, a jego liczba chromatyczna $\chi(G) = k$. Można również stosować oznaczenie $k$-kolorowalny, lecz dla większej ścisłości będziemy używać pojęcia $k$-kolorowalny$(v)$.

Dla niektórych grafów znana jest wartość liczby chromatycznej:

• $\chi(K_n) = n$,
• $\chi(N_n) = 1$,

a dla grafu dwudzielnego $G$:

• $\chi(G) = 2$.

Liczba chromatyczna grafu nie może przekraczać liczby wierzchołków $n$ tego grafu, a jeśli graf zawiera podgraf $K_r$, to jego liczba chromatyczna nie może być mniejsza od $r$.

Pewne twierdzenie dotyczy grafów prostych i wykorzystuje stopień każdego wierzchołka:

• Jeśli $G$ jest grafem prostym, w którym majwiększym stopniem wierzchołka jest $\Delta$, to graf $G$ jest $(\Delta + 1)$-kolorowalny$(v)$.

Z tego twierdzenia wynika silniejsze znane jako twierdzenie Brooksa:

• Jeśli $G$ jest spójnym grafem prostym, nie będącym grafem pełnym i jeśli największy stopień wierzchołka grafu $G$ wynosi $\Delta$ (gdzie $\Delta \ge 3$), to $G$ jest $k$-klolorowalny$(v)$ (Brooks, 1941).

Grafy planarne

Niewiele wiemy o liczbie chromatycznej dowolnego grafu. Możemy natomiast ograniczyć nasze zainteresowanie do grafów planarnych. Z biegiem czasu udowodniono, że każdy planarny graf prosty jest $6$-kolorowalny$(v)$, następnie okazało się, że jest również $5$-kolorowalny$(v)$ (Heawood, 1890). W końcu wykazano prawdziwość kolejnej cechy znanej popularnie pod nazwą zagadnienie czterech barw:

• Każdy planarny graf prosty jest $4$-kolorowalny$(v)$ (Appel i Haken, 1976).

Podane twierdzenie jest o tyle ciekawe, że nie przedstawiono elementarnego dowodu pokazującego prawdziwość zagadnienia. Dopiero w 1976 roku został opracowany przez K. Appela i W. Hakena pierwszy, prawdziwy dowód tego twierdzenia. Opierał się on w główniej mierze na pracy komputera i rozważał ponad $1500$ przypadków.

Kolorowanie krawędzi grafu

Graf $G$ jest $k$-kolorowalny$(e)$, jeśli jego krawędzie można pokolorować $k$ kolorami tak, aby żadne dwie sąsiednie krawędzie grafu $G$ nie miały takiego samego koloru. Jeśli graf $G$ jest $k$-kolorowalny$(e)$, a nie jest $(k-1)$-kolorowalny$(e)$, to wtedy jego indeks chromatyczny $\chi'(G)$ jest równy $k$.

Możemy wyznaczyć indeks chromatyczny poszczególnych typów grafów, w zależności od liczby wierzchołków $n$.

1. Dla parzystej liczby $n$: $\ \chi'(C_n)=2$.
2. Dla nieparzystej liczby $n$ (gdzie $n \ne 1$): $\ \chi'(C_n)=3$.
3. Dla $n \ge 4$: $\ \chi'(W_n)=n-1$.
4. Dla nieparzystego $n$ (gdzie $n \ne 1$): $\ \chi'(K_n)=n$.
5. Dla parzystego $n$: $\ \chi'(K_n)=n-1$.
6. Dla grafu $K_{r,s}$: $\ \chi'(K_{r,s}) = \max(r,s)$.
7. Dla kubicznego grafu hamiltonowskiego $G$: $\ \chi'(G)=3$.

Niektóre twierdzenia dokładnie przybliżają wartość indeksu chromatycznego. Jedno sformułowane przez V. G. Vizinga szacuje wartość indeksu chromatycznego grafu prostego.

• Jeśli $G$ jest grafem prostym, w którym największy stopień wierzchołka wynosi $\Delta$, to $\Delta \le \chi'(G) \le \Delta + 1$ (Vizing, 1964).

Z kolei twierdzenie D. Königa wyznacza dokładną wartość indeksu chromatycznego dla grafu dwudzielnego.

• Jeśli w grafie dwudzielnym największy stopień wierzchołka wynosi $\Delta$, to $\chi'(G) = \Delta$ (König, 1916).

Następne dotyczy regularnych grafów prostych.

• Jeśli $G$ jest regularnym grafem prostym którego stopień jest równy $\Delta$, to $\chi'(G)=\Delta + 1$.

Ciekawym faktem jest to, że twierdzenie o czterech barwach jest równoznaczne stwierdzeniu, że dla każdej kubicznej mapy $G$, indeks chromatyczny $\chi'(G)=3$.

Wielomiany chromatyczne

W tej części poruszymy tematykę pewnej funkcji, której analiza wykaże wiele istotnych właności grafów. Następnie przy pomocy interaktywnej prezentacji doświadczalnie zbadamy wartości tej funkcji.

Oznaczmy $G$ jako graf prosty, $k$ niech będzie liczbą dostępnych kolorów, wtedy $P_G(k)$ (wielomian chromatyczny grafu $G$) jest liczbą sposobów pokolorowania wierzchołków grafu $G$ $k$ kolorami tak, aby żadne dwie sąsiednie wierzchołki nie miały takiego samego koloru. Oczywiste jest, że jeśli $k < \chi(G)$, to $P_G(k)=0$, a jeśli $k > \chi(G)$, to $P_G(k) > 0$.

Jeśli drzewo $G$ ma $1$ wierzchołek, to wtedy $P_G(k) = k$, jeśli ma $2$ wierzchołki, to $P_G(k) = k(k-1)$, jeśli $3$ to $P_G(k)=k(k-1)^2k$, a jeśli posiada $4$ wierzchołki, wtedy $P_G(k) = k(k-1)^3$. Możemy zauważyć tutaj pewną zależność od ilości wierzchołków drzewa, co dopuszcza możliwość istnia pewnego wzoru określającego wartość wielomianu $P_G(k)$. Okazuje się, że to prawda, a sam wzór dotyczy dowolnego drzewa. Ma on postać: $$P_G(k) = k(k-1)^{n-1}$$ gdzie $n$ oznacza ilość wierzchołków drzewa.

Podobna zależność występuję w przypadku grafów pełnych, w tym przypadku liczba możliwości pokolorowania kolejnego wierzchołka zmniejsza się o $1$.

W grafach pełnych $K_n$ mających kolejno $1$ wierzchołek $P_{K_1}(k)=k$, $2$ wierzchołki $P_{K_2}(k)=k(k-1)$, $3$ wierzchołki $P_{K_3}(k)=k(k-1)(k-2)$. Zatem końcowy wzór dla grafu pełnego $K_n$ będzie miał postać: $$P_{K_n}(k) = k(k-1)(k-2) \ldots (k-n+1) = \frac{k!}{n!}$$ gdzie $n$ oznacza liczbę wierzchołków.

Wartość wielomianu $P_G(k)$ dla grafu prostego $G$ pomaga wyzaczyć twierdzenie:

• Niech $G$ będzie grafem prostym i niech $G - e$ będzie grafem otrzymanym przez usunięcie krawędzi $e$, a $G \setminus e$ będzie grafem powstałym przez ściągnięcie krawędzi $e$. Wówczas $$P_G(k)=P_{G-e}(k) - P_{G \setminus e}(k)$$.