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