W

M

P

-U

K

SW

Wykład 6

Kolorowanie wierzchołków i krawędzi

6.1. Kolorowanie wierzchołków

Definicja 6.1. Przyporządkowanie ψ : V (G) → {1, 2, . . . , k} wierzchołkowi
grafu G jednego z k kolorów nazywamy k-kolorowaniem wierzchołków
grafu G.

Definicja 6.2. Mówimy, że kolorowanie wierzchołków jest właściwe, jeśli
żadne dwa różne wierzchołki nie są tego samego koloru.

Definicja 6.3. Właściwe k-kolorowanie, to podział (V

1

, V

2

, . . . , V

k

) zbio-

ru wierzchołków V (G) taki, że zbiory V

i

indukują grafy puste.

Uwaga 6.1. W dalszej części wykładu, jeśli nie zazanczymy inaczej, mówiąc
k

-kolorowanie, będziemy mieli na myśli k-kolorowanie właściwe.

Definicja 6.4. Graf jest k-kolorowalny wierzchołkowo, jeśli istnieje wła-
ściwe k-kolorowanie wierzchołków.

Przykład 6.1. Graf prosty

1) jest 1-kolorowalny, wtedy i tylko wtedy, gdy jest

grafem pustym;

2) jest 2-kolorowalny, wtedy i tylko wtedy, gdy jest

grafem dwudzielnym;

3) K

n

jest n-kolorowalny.

1

2

3

4

5

Rys. 6.1. Graf K

5

Definicja 6.5. Liczba chromatyczna χ(G) grafu
G

, to najmniejsza liczba k, dla którego graf jest k-

-kolorowalny.

Definicja 6.6. Mówimy, że graf G jest k-chroma-
tyczny, jeśli χ(G) = k.

Przykład 6.2. Graf z rysunku

6.1

ma liczbę chro-

matyczną równą χ(G) = 3.

1

2

2

2

3

3

3

Rys. 6.2.

Definicja 6.7. Graf jest krytyczny, jeśli χ(H) < χ(G) dla każdego właści-
wego podgrafu H grafu G.

Definicja 6.8. Graf G jest k-krytyczny, jeśli jest krytyczny oraz k-chroma-
tyczny.

RK

31

W

M

P

-U

K

SW

32

Wykład 6. Kolorowanie wierzchołków i krawędzi

Przykład 6.3. Liczby chromatyczne grafu G oraz jego pografów H

i

(rysu-

nek

6.3

), i = 1, 2, 3 są równe odpowiednio χ(G) = 3, χ(H

1

) = 2, χ(H

2

) = 2,

χ

(H

3

) = 1. Graf G jest 3-krytyczny.

1

2

3

(a)

1

1

2

(b)

1

1

2

(c)

1

1

1

(d)

Rys. 6.3. (a) Graf G oraz jego podgrafy (b) H

1

, (c) H

2

, (d) H

3

Przykład 6.4. Liczba chromatyczna grafu G = C

5

(rysunek

6.4

(a)) jest

równa χ(C

5

) = 3. Liczba chromatyczna największego podgrafu H (rysunek

6.4

(b)) grafu G jest równa χ(H) = 2.

1

2

1

1

3

(a)

1

2

1

1

2

(b)

Rys. 6.4. (a) Graf G = C

5

oraz (b) maksymalny podgraf H grafu G

Wszyskie cykle C

2k+1

są k-krytyczne.

Przykład 6.5 (Graf Gr¨

otzscha). Liczba chromatyczna grafu Gr¨otzscha

jest równa χ(G) = 4 natomiast jego maksymalnego podgrafu H, χ(H) = 3.

1

3

1

3

4

2

2

2

2

2

1

Rys. 6.5. Graf Gr¨otzscha

Uwaga 6.2. Każdy graf G k-chromatyczny posiada k-krytyczny podgraf
(rysunek

6.6

).

Twierdzenie 6.1. Jeśli graf jest k-krytyczny, to δ ­ k − 1.

Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie

W

M

P

-U

K

SW

6.2. Kolorowanie krawędzi

33

1

2

2

2

3

3

3

H

Rys. 6.6. Zaznaczony podgraf H ⊂ G jest podgrafem 3-krytycznym grafu G

Dowód.

Załóżmy, że graf G jest k-krytyczny, ale δ ­ 2. Weźmy wierzchołek

x

taki, że d(x) = δ(G). Z krytyczności grafu G wynika, że χ(Gr{x}) ¬ k −1.

Zatem graf G r {x} można pokolorować właściwie k − 1 kolorami. Ponadto
wierzchołek x ma co najmniej jeden nieużyty kolor. Kolorujemy krawędź x
na ten kolor otrzymując właściwe (k − 1)-kolorowanie całego podgrafu G.
Sprzeczność z tym, że χ(G) = k.



Wniosek 6.1. Jeżeli χ(G) = k, to istnieje k wierzchołków stopnia co naj-
mniej

k

− 1.

Dowód.

Oznaczmy przez H, k-krytyczny podgraf grafu G. Z twierdzenia

6.1

wiemy, że minimalny stopień w H, δ(H) ­ k − 1, a ponieważ H ma co naj-
mniej k wierzchołków, bo χ(H) = k, natomiast stopnie tych wierzchołków są
zawsze nie mniejsze od δ(H).



Wniosek 6.2. Liczba chromatyczna χ(G) oraz maksymalny stopień wierz-
chołka

∆(G) w grafie G spełniają nierówność

χ

(G) ¬ ∆(G) + 1.

Dowód.

Przypuśćmy, że χ(G) = k. Z wniosku

6.2

wynika, że istnieje wierz-

chołek stopnia co najmniej k − 1. Wobec tego χ(G) = k = 1 + k − 1 ¬
1 + d(x) ¬ 1 + χ(G).



Przykład 6.6. Niech G = K

n

. Maksymalny stopień wierzchołka w grafie

K

n

jest równy ∆(K

n

) = n − 1, Liczba chromatyczna χ(K

n

) = n, χ(K

n

) =

∆(K

n

) + 1.

Teraz niech G = C

2k+1

. Mamy ∆(C

2k+1

) = 2 oraz χ(C

2k+1

) = 3, więc rów-

nież χ(C

2k+1

) = ∆(C

2k+1

) + 1.

Twierdzenie 6.2 (Brooksa, 1941). Jeśli graf G jest spójny i różny od gra-
fów

K

n

i

C

2k+1

, to liczba chromatyczna

χ

(G) ¬ ∆(G).

6.2. Kolorowanie krawędzi

Definicja 6.9. Przyporządkowanie η : E(G) → {1, 2, . . . , k} każdej krawę-
dzi grafu G jednego z k kolorów nazywamy k-kolorowaniem krawędzi
grafu prostego G.

Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie

W

M

P

-U

K

SW

34

Wykład 6. Kolorowanie wierzchołków i krawędzi

Definicja 6.10. Jeśli żadne dwie właściwe krawędzie w grafie nie są tego
samego koloru, to k-kolorowanie η nazywamy kolorowaniem właściwym.

Uwaga 6.3. k-kolorowanie krawędzi można także zdefiniować jako podział
(E

1

, E

2

, . . . , E

k

) zbioru krawędzi E(G), gdzie E

i

oznacza krawędzie w kolo-

rze i. Wówczas właściwe k-kolorowanie jest takim kolorowaniem, w którym
każdy zbiór E

i

jest zbiorem rozłącznym krawędzi.

Definicja 6.11. Graf jest k-kolorowalny krawędziowo, jeśli ma właściwe
k

-kolorowanie krawędzi.

Definicja 6.12. Najmniejszą liczbę k, dla której graf G jest k-kolorowalny
krawędziowo nazywa się indeksem chromatycznym (lub krawędziową
liczbą chromatyczną). Indeks chromatyczny oznaczamy przez χ

′

(G).

Definicja 6.13. Graf G jest k-chromatyczny kra-
wędziowo, jeżeli indeks chromatyczny χ

′

(G) = k.

Przykład 6.7. Indeks chromatyczny grafu G przed-
stawionego na rysunku

6.7

jest równy χ

′

(G) = 4.

Nie ma właściwego kolorowania krawędzi tego grafu
trzema kolorami.

1

2

3

4

2

3

1

Rys. 6.7.

Definicja 6.14. Mówimy, że kolor i jest reprezentowany w wierzchoł-
ku x jeśli jest incydentny z krawędzią koloru i.

Fakt 6.1.

1) Graf ma zawsze m-kolorowanie właściwe krawędzi, gdzie m = |E(G)|.
2) χ

′

(G) ­ ∆(G).

3) Jeżeli graf ma właściwe kolorowanie krawędzi i l ­ k, to G ma również

właściwe

l-kolorowanie krawędzi.

Twierdzenie 6.3 (Vizinga, 1964). Jeżeli graf G jest prosty, to

∆(G) ¬ χ

′

(G) ¬ ∆(G) + 1.

Przykład 6.8. Pokażemy, że χ

′

(K

2n+1

) = 2k +1. Zauważmy, że χ(K

2k+1

) ­

∆(K

2k+1

) = 2k. Z twierdzenia Vizinga

2k ¬ χ(K

2k+1

) ¬ 2k + 1.

Chcemy pokazać, że K

2k+1

nie można pokolorować właściwie za pomocą

2k kolorów. Maksymalna liczba krawędzi K

2k+1

w jednym kolorze jest równa

k

(rysunek

6.8

). Liczba krawędzi, którą możemy pokolorować właściwie ma-

jąc 2k kolorów jest równa k · 2k = 2k

2

. Graf K

2k+1

ma



2k+1

2



=

2k(2k+1)

2

=

k

(2k + 1) = 2k

2

+ k krawędzi. Pozostaje więc k krawędzi niepokolorowanych.

Zatem χ

′

(G) 6= 2k.

Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie

W

M

P

-U

K

SW

6.2. Kolorowanie krawędzi

35

1

1

2

2

3

3

4

4

5

5

Rys. 6.8.

Twierdzenie 6.4 (K¨

oniga, 1916). Jeżeli w grafie dwudzielnym G mksy-

malny stopień wierzchołka jest równy

∆(G), to

χ

′

(G) = ∆(G).

Dowód.

Przeprowadzimy dowód indukcyjny ze względu na liczbę wierzchoł-

ków. Przyjmijmy ∆ = ∆(G). Niech ∆ = 1. Wówczas χ

′

(G) = 1.

Załóżmy, że jeśli w grafie G brakuje jednej krawędzi, to χ

′

(G r {e}) = ∆.

Chcemy pokazać, że wszystkie krawędzie grafu G również można pokolorować
za pomocą ∆ kolorów. Załóżmy ponadto, że wszystkie krawędzie z wyjątkiem
krawędzi {u, v} zostały pokolorowane przy użyciu ∆ kolorów. Rozważmy
krawędzie wychodzące z wierzchołka u. Maksymalna liczba pokolorowanych
krawędzi jest równa ∆ − 1 (wszystkie z wyjątkiem krawędzi {u, v}). Rozważ-
my teraz wierzchołek v. Znów maksymalna liczba krawędzi pokolorowanych
jest równa ∆ − 1.

1) Jeśli brakujący kolor w u jest taki sam, jak brakujący kolor w v, to nim

kolorujemy krawędź {u, v}.

2) Niech brakujący kolor w u będzie różny od brakującego koloru w v

(powiedzmy, że brakujący kolor w u, to α,natomiast brakujący kolor w v, to
β

). Rozważmy spójny podgraf H grafu dwudzielnego G, w którym znajdują

się te wierzchołki, do których można dojść z u po krawędziach koloru α i β.
Zauważmy, że w H nie ma wierzchołka v. Zamieńmy w podgrafie H kolor
α

na kolor β i β na α. Z wierzchołka v krawędzie mają niezmieniony kolor.

Teraz brakujący kolor w u, to β i jest to ten sam kolor, którego brakuje
w wierzchołku v, czyli mamy sytuację 1).



Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie