WYKŁAD 2.

Kolorowanie wierzchołków

(Uogólnienie problemu ZOO)

Kliki i zbiory niezależne

• W nazywamy

kliką

, gdy G[W] jest

pełny.

• W nazywamy

zbiorem niezależnym

,

gdy G[W] jest pusty.

• Liczba klikowa

ω(G)= ω to moc

największej kliki w grafie G.

• Liczba niezależności

α(G)=α to moc

największego zbioru niezależnego w G.

Przykład

ω=3

α=3

Liczba chromatyczna

• Liczba chromatyczna

χ(G)= χ to

najmniejsza

liczba k, taka że zbiór V

można rozbić na k rozłącznych zbiorów
niezależnych.

• Inaczej,

minimalna

liczba kolorów, przy

pomocy których można pomalować
wierzchołki grafu, tak by końce każdej
krawędzi miały różne kolory.

Graf Petersena: χ=3

k-kolorowalność = k-

dzielność

to mówimy, że graf jest

k-kolorowalny

, albo

k-

dzielny.

• Mówiąc k-dzielny, mamy zwykle na myśli

ustalony podział V na k zbiorów
niezależnych V_1,...,V_k.

• Graf

pełny dwudzielny

K(m,n) to graf

dwudzielny o dwupodziale (V_1,V_2), przy
czym |V_1|=n a |V_2|=m, posiadający

wszystkie mn

krawędzie o jednym końcu w

V_1 a drugim w V_2.

k





Jeśli

Ilustracja: k=3

Ilustracja: K(3,4)

Oszacowania dolne

• Grafy

doskonałe

: χ(G[W])=ω(G[W]) dla

wszystkich W.

• Wszystkie grafy pełne oraz puste są doskonałe,

bo χ(K_n)= ω(K_n)=n i χ(N_n)= ω(N_n)=1.

• Wszystkie grafy dwudzielne są doskonałe, bo

χ(G)= ω(G)=2 (o ile G jest niepusty).

• Dopełnienia grafów dwudzielnych też są

doskonałe (

ćwiczenie

).











|

|V



Słaba hipoteza Berge’a

• Lovász 1972:

Graf jest doskonały wgdy

jego dopełnienie jest doskonałe.

• Lovász pokazał mocniejszy fakt:
G jest doskonały wgdy dla każdego

W

 





 





W

G

W

G

W









Cykle parzyste

• Cykle

parzyste (nieparzyste)

to cykle

o parzystej (nieparzystej) długości.

C_4

•

Długość

cyklu mierzymy liczbą

krawędzi.

•

Cykle parzyste są

dwudzielne.

Cykle nieparzyste

• Dla cykli nieparzystych

χ=3.

C_5

• Ponadto, cykle nieparzyste

długości większej niż 3 nie są
doskonałe, bo

ω=2.

Mocna hipoteza Berge’a

1966

• Chudnovsky, Robertson, Seymour,

and Thomas 2002

:

• Graf jest doskonały wgdy ani on

ani jego dopełnienie nie zawierają
indukowanych cykli nieparzystych
dłuższych niż 3.

• Dowód na 200 stron pomijamy!

Grafy „anty-doskonałe”

• Mycielski 1955

: Dla dowolnej liczby

naturalnej k

≥

2 istnieje graf G_k, taki że

ω(G_k)=2, a χ(G_k)=k.

• Dowód indukcyjny

: G_2=K_2.

• Załóżmy, że G_k jest już skonstruowany na

wierzchołkach v_1,...,v_n.

• Utwórzmy G_{k+1} przez dodanie n+1

nowych wierzchołków u_1,...,u_n oraz v i

połączenie każdego u_i z v oraz ze

wszystkimi sąsiadami wierzchołka v_i w G_k.

Ilustracja dowodu Tw.

Mycielskiego

v_1

v_2

u_2

u_1

v

G_2

G_3

Ilustracja – ciąg dalszy

v_1

v_2

v_3

v_4

v_5

v

u_5

u_1

u_2

u_3

u_4

G_4

G_{k+1} nie zawiera K_3

• Gdyby zawierał, to składałby się z 1

nowego wierzchołka – u_i i dwóch

„starych” – v_j,v_l.

• Skoro jednak u_iv_j i u_iv_l są

krawędziami grafu G_{k+1}, to

v_iv_j i v_iv_l są krawędziami w G_k.

• Zatem v_i,v_j,v_l tworzą trójkąt w

G_k – sprzeczność.

Ilustracja

v_j

v_l

u_i

v_i

χ(G_{k+1})=k+1

• Weźmy dowolne k-kolorowanie G_k,

powtórzmy kolor v_i na u_i, a v
pomalujmy nowym, (k+1)-szym kolorem.

• Gdyby dało się pomalować G_{k+1} k

kolorami, to na u_1,...,u_n wystąpiłoby
tylko k-1 kolorów (k-ty kolor na v).

• Kolory z u_1,...,u_n można jednak

przenieść na v_1,...,v_n otrzymując (k-1)-
kolorowanie grafu – sprzeczność.



Ilustracja

v_1

v_2

v_3

v_4

v_5

v

u_5

u_1

u_2

u_3

u_4

Oszacowania górne

• Δ(G)= Δ to największy stopień

wierzchołka w grafie.

• Algorytm zachłanny

(„greedy”)

maluje kolejno wierzchołki
pierwszym wolnym kolorem.

1











1







n



Greedy -- ilustracja

Greedy -- ilustracja

Greedy -- ilustracja

Greedy -- ilustracja

Greedy -- ilustracja

Greedy -- ilustracja

Greedy -- ilustracja

Kiedy χ=Δ+1 ?

• Cykle nieparzyste i

grafy pełne

.

• Jeśli G jest niespójny, to znaczy istnieje

podział V na A i B bez A-B krawędzi, to

χ(G)=max(χ(G[A]), χ(G[B]),

Δ(G) = max(Δ(G[A]), Δ(G[B]).

• Grafy G, w których

Δ(G)=2

i

choć jedna

składowa jest cyklem nieparzystym.

• Grafy G, w których choć jedna składowa

jest grafem pełnym K_{Δ(G)+1}.

Grafy niespójne -

kolorowanie

A

B

B1

B

2

Twierdzenie

Brooksa

(1941)

Jeśli

spójny

graf G nie jest ani

nieparzystym cyklem, ani grafem
pełnym, to

 

 

G





G



Przypadek Δ=2

• Przypadek Δ=2 obejmuje tylko

ścieżki

i

cykle

-- wśród nich tylko

cykle nieparzyste mają χ=3.

G nieregularny

• Jeśli G

nie

jest

regularny

, to

ustawmy wierzchołki w kolejności
v_1,...,v_n, tak że d(v_n)< Δ , a dla
każdego i=1,...,n-1,

v_i ma sąsiada „na prawo”.

• Wtedy algorytm zachłanny użyje

co najwyżej Δ kolorów.

Ilustracja

Ilustracja – c.d.

G ma wierzchołek cięcia

• Wierzchołek v grafu spójnego G nazywamy

wierzchołkiem cięcia

, gdy G-v nie jest spójny.

• To znaczy istnieje podział V na A i B, |A|,|B|

>1, A∩B={v}, bez krawędzi pomiędzy A-
{v} i B-{v}.

• Wtedy

χ(G)=max(χ(G[A]), χ(G[B])

oraz

Δ(G) ≥ max(Δ(G[A]), Δ(G[B]).

• Pokazać, że w tym przypadku

χ(G)

≤

Δ(G)

(

ćwiczenia

).

Ilustracja

v

A

B

Dowód Tw. Brooksa

• „Z głowy” mamy już przypadki: Δ=2, G

nieregularny i G z wierzchołkiem cięcia.

• Niech teraz G będzie dowolnym grafem

Δ-regularnym, bez wierzchołków cięcia,

Δ ≥ 3, n=|V(G)|, spełniającym

założenia twierdzenia.

• Ponieważ G nie jest grafem pełnym, to

E

vw

E

uw

E

uv

w

v

u









,

,

:

,

,

Przypadek I

G-{u,v}=G[V-{u,v}] jest spójny.

• Ustaw wierzchołki w kolejności

u,v,v_1,...,v_{n-3},w tak, że dla
każdego i=1,...,n-3, v_i ma sąsiada
„na prawo”.

• Algorytm zachłanny pomaluje u i v tym

samym kolorem i dlatego wystarczy Δ
kolorów do pomalowania całego grafu.

Ilustracja

u

v

w

Przypadek II

Istnieje podział V na A i B, |A|,|

B|>2 :

•

Łatwo pokazać, że oba podgrafy,

G[A] i

G[B],

można pomalować Δ kolorami

(

ćwiczenia

).

• Jeśli

oba podgrafy

można pomalować

tak,

by u i v miały różne kolory

, to potem

można „zgrać” kolory uzyskując Δ-
kolorowanie całego grafu G.





























2

2

B

A

E

 

v

u

B

A

,





Ilustracja

u

v

A

B

Przypadek II – c.d.

• Przypuśćmy, że w każdym kolorowaniu

podgrafu G[A], wierzchołki

u i v otrzymują

ten sam kolor

.

• Wtedy, pamiętając, że uv

nie

jest krawędzią,

mamy

w G[A]

d(u),d(v)

≥

Δ-1.

• Ponieważ stopnie u i v w obu podgrafach są

pomiędzy 1 i Δ-1 (w przeciwnym razie byłby

wierzchołek cięcia lub G nie byłby spójny),

to

w G[B] d(u)=d(v)=1.

• Ponieważ

Δ

≥

3,

można znaleźć kolorowanie

podgrafu G[B], w którym

u i v są tego

samego koloru

, i znów „zgrać” kolory. 

Ilustracja

u

v

A

B