KOLOROWANIE JAKO NARZĘDZIE UNIKANIA KONFILKTÓW

dr Konstanty Junosza - Szaniawski

ZADANIA

2. Wykazać, że w planarnym grafie bez trójkątów o n ≥ 3 wierzchołkach jest co najwyżej 2n — 4 krawędzi.

4. Wykazać, że dwa ostatnie grafy z zadania 1 nie są planarne.

5. Wykazać, że w grafie planarnym bez trójkątów minimalny stopień nie przekracza 3.

6. Wykazać (nie korzystając z twierdzenia o czterech kolorach), że jeśli planarny graf G nie zawiera trójkąta to χ(G) ≤ 4.

Wskazówki

1. Znaleźć pokolorowanie grafów na najmniejszą możliwą liczbę kolorów oraz podać argument, dla którego mniej kolorów nie wystarcza.

2. Skorzystać z Formuły Eulera: n — e + f = 2 i faktu, że każda ściana jest ograniczona przez cykl długości co najmniej cztery czyli 2e ≥ 4f.

3. Skorzystać z Formuły Eulera i faktu, że 2e ≥ k • f.

4. 
   Porównać liczbę krawędzi z ograniczeniami z zadania 1 i 2.

6. Znaleźć ograniczenie na liczbę kolorów użytych przez algorytm zachłanny zastosowany do ciągu wierzchołków, który można skonstruować dzięki nierówności z zadania 4.

Odpowiedzi

1. 4, 3, 2, 4, 3, 2.

2. Każda ściana jest ograniczona przez co najmniej 4 krawędzie, przy czym każda krawędź leży na brzegu co najwyżej dwóch ścian. Zatem podwojona liczba krawędzi wynosi co najmniej 4 razy liczba ścian: 2e ≥ 4f. Jeśli z formuły Eulera n — e + f = 2 wyznaczymy liczbę ścian f = 2 — n + 2, wstawimy do poprzedniej nierówności i uprościmy, to otrzymamy e ≤ 2n — 4.

3. 
   Zadanie można rozwiązać podobnie do poprzedniego z tą różnicą, że każda ściana jest ograniczona przez przynajmniej k krawędzi. Zatem mamy nierówność 2e ≥ k • f. Po wstawieniu f = 2 — n + e, z formuły Eulera otrzymujemy

4. Pierwszy graf nie zawiera trójkątów, zatem można skorzystać z nie­równości z zadania 1. Graf planarny o 6 wierzchołkach może mieć co najwyżej 2 • 6 — 4 = 8 krawędzi. Rozważany graf ma 9 krawędzi, więc nie jest planarny.

Drugi graf ma talię (długość najkrótszego cyklu) równą 5. Graf planarny o talii 5 i 10 wierzchołkach ma co najwyżej

krawędzi. Graf z rysunku ma 15 krawędzi więc nie jest planarny.

5. 
   
   Szacujemy sumę stopni z dwóch stron, Z jednej strony jest co najmniej równa minimalnemu stopniowi pomnożonemu przez liczbę wierzchołków. Z drugiej strony jest równa podwojonej liczbie krawędzi. Korzystamy z nierówności na liczbę krawędzi w planarnym grafie bez trójkątów i otrzymujemy:

Minimalny stopień jest liczbą całkowitą, zatem ostatecznie δ(G) ≤ 3.

6. Dzięki nierówności z zadania 4 wiemy, że w grafie planarnym bez trójkątów istnieje wierzchołek stopnia co najwyżej 3. Usuńmy go z grafu. Otrzymamy nowy graf planarny bez trójkątów. Ten graf również będzie zawierał wierzchołek stopnia co najwyżej 3, Usuńmy go. Postępujemy tak dalej aż usuniemy cały graf wierzchołek po wierzchołku. Teraz pokolorujmy początkowy graf w kolejności odwrotnej do usuwania, przydzielając każdemu wierzchołkowi najmniejszy możliwy kolor. Każdy wierzchołek w momencie usuwania był stopnia co najwyżej 3 to znaczy, że gdy go kolorujemy ma co najwyżej trzech pokolorowanych sąsiadów, czyli co najwyżej 3 kolory nie dozwolone. Jeśli mamy do dyspozycji cztery kolory to jeden z nich jest dostępny i możemy ten wierzchołek pokolorować, W ten sposób wszystkie wierzchołki grafu możemy pokolorować. Zatem liczba chromatyczna grafu planarnego bez trójkątów nie przekracza 4.

Zeszyt ćwiczeń

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

4

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

---