Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 10
Kolorowanie grafów
k
Mówimy, że graf jest (wierzchołkowo) -kolorowalny, jeżeli jego
k
wierzchołki można pokolorować za pomocą kolorów (lub
mniej), tak aby sąsiednie wierzchołki miały różne barwy. Minimalną
liczbę kolorów potrzebną do pokolorowania grafu nazywamy liczbą
chromatyczną grafu.
Pytanie: Czy każdą mapę płaską można pokolorować za pomocą 4 barw jest równoważne
pytaniu czy każdy graf płaski jest 4 kolorowalny.
Twierdzenie o 6 barwach
Każdy graf plaski można pokolorować za pomocą 6 barw.
Lemat
Każdy graf płaski zawiera wierzchołek stopnia co najwyżej 5.
Dowód lematu:
Załóżmy, że każdy wierzchołek ma stopień przynajmniej 6. Wówczas 2Ke"6W tzn.
K e"3Wą3W-6 . Z poprzedniego wykładu wiemy, że dla grafów płaskich K d"3W-6 .
Sprzeczność.
Dowód twierdzenia o 6 barwach:
Indukcja ze względu na liczbę wierzchołków. Dla n=1,...6 jest oczywiste. Załóżmy, że
n
twierdzenie prawdziwe dla ustalonego . Pokażemy, że prawdziwe jest też dla n�ą1 .
G
Rozważmy graf mający n�ą1 wierzchołków. Na mocy lematu graf zawiera wierzchołek
stopnia co najwyżej 5. Odrzućmy (na chwilę) ten wierzchołek. Z założenia indukcyjnego
pozostała część jest 6 kolorowalna. Wybrany wierzchołek ma 5 sąsiadów lub mniej, a więc
jest dla niego wolny kolor.
Aby udowodnić twierdzenie o 5 barwach trzeba krok
indukcyjny przeprowadzić subtelniej. Oczywiście można
v
założyć, że usunięty chwilowo wierzchołek ma
v
dokładnie 5 sąsiadów. Usuńmy wierzchołek , a dwóch
jego sąsiadów u , w sklejmy w jeden wierzchołek.
Powstały w ten sposób graf ma mniej wierzchołków więc z założenia
jest 5 kolorowalny. Pokolorujmy go po czym rozsuńmy u ,w i
v v
dodajmy usunięty . Wierzchołek ma dokładnie 5 sąsiadów, ale
u , w mają ten sam kolor, a więc sąsiedzi wykorzystują co najwyżej 4 kolory. Pozostaje
v
wolny kolor dla .
u w
Ale uwaga! Co dzieje się jeżeli oraz to sąsiedzi? Po sklejeniu powstaje pętla
tzn. wierzchołek u ,w musi mieć inny kolor niż wierzchołek u , w !!!
v u
Czy można wybrać sąsiadów u , w wierzchołka tak aby nie sąsiadował z
w ? Gdyby każda para u ,w sąsiadowała ze sobą to tych 5 sąsiadów stanowiłoby graf
K5 K5
. Z założenia graf jest płaski, a więc nie zawiera , czyli można wybrać u , w w
sposób właściwy.
Twierdzenie (?) o czterech barwach (Appel, Haken, 1976)
Każdy graf płaski można pokolorować 4 barwami (?).
Twierdzenie (Brooks, 1951)
S śąS �ą1źą
Jeżeli każdy wierzchołek ma stopień mniejszy bądz
równy , to graf jest
kolorowalny.
Dowód:
Wez
my np. książkę V. Bryant Aspekty kombinatoryki. (łatwy)
Cn
Dla S=2 istnieją przykłady  cykle nieparzyste , które nie dadzą się dwukolorować
śąS�ą1źą S
choć st v=2 (a więc nie można zastąpić przez ).
K
S
Dla Są2 też nie można poprawić bo np. ma stopień wierzchołka , a nie jest
S �ą1
S kolorowalny.
Twierdzenie (Brooks cd.)
śąS �ą1źą S
Twierdzenie można poprawić z na zawsze, chyba, że mamy do czynienia z
jednym z dwóch powyższych kontrprzykładów.
k
Mówimy, że graf jest krawędziowo kolorowalny, jeśli krawędzie można pokolorować za
k
pomocą kolorów tak, aby krawędzie tego samego koloru nie miały wspólnych
wierzchołków.
Twierdzenie Vizinga
S
Jeśli każdy wierzchołek ma stopień mniejszy bądz
równy to graf
śąS �ą1źą
jest krawędziowo kolorowalny tzn. jego indeks chromatyczny
S śąS �ą1źą
jest równy albo .
K
Indeks chromatyczny dla :
n
�ą' śą K1źą=0 �ą ' śąK3źą=3 �ą' śą K5źą=5
�ą' śą K2źą=1 �ą' śąK4źą=3 �ą' śą K6źą=5
Twierdzenie dla ne"2
n gdy n nieparzyste
�ą' śą Knźą=
n-1 gdy n parzyste
Dowód:
K
Przedstawmy w postaci wielokąta foremnego wraz z przekątnymi.
n
n
Niech parzyste. Pokolorujmy wszystkie krawędzie wychodzące z
ustalonego wierzchołka za pomocą n-1 kolorów. Zauważmy, że dla ( n
parzystego) każda inna krawędz
(bok lub przekątna) jest równoległa do jednej
z tych krawędzi. Przyjmując, że krawędzie równoległe mają ten sam kolor
otrzymujemy żądane pokolorowanie.
n
Niech nieparzyste. Znów przyjmujemy, że krawędzie równoległe mają
n-1
v1 vi
ten sam kolor. Dla ustalonej krawędzi jest równoległych do
2
niej licząc z nią samą. Ponieważ wszystkich krawędzi jest
nśą n-1źą
n-1
n
n
, więc daje to kolorów.
= =n
śą źą
śą źą
2 2
2
Dlaczego nie wystarczy n-1 kolorów?
nśą n-1źą
Skoro wszystkich krawędzi jest to przy n-1 kolorach na jeden kolor wypada
2
n n�ą1
n
średnio krawędzi, a skoro nieparzyste, to w jednym kolorze musi być
2 2
n�ą1
2 =n�ą1
krawędzi. Końce tych krawędzi są różne więc mamy wierzchołków.
2
Sprzeczność.