Połączenie dwóch prostych grafów planarnych ma liczbę chromatyczną $\leq 12$
Rozważ wykres $G$będący połączeniem dwóch prostych grafów planarnych znajdujących się na tym samym zbiorze wierzchołków. Chcę pokazać$\chi(G) \leq 12$.
Twierdzenie o czterech kolorach wskazuje, że liczba chromatyczna wykresu planarnego jest mniejsza niż 4, a także dla wykresów ogólnych $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Ale to dałoby tylko górną granicę 16. Czy jest coś szczególnego w grafie planarnym, co pomaga zmniejszyć tę granicę?
Odpowiedzi
Od $G_1$ i $G_2$ są płaskie, mamy $|E(G_1)| \le 3|V(G_1)|-6$ i $|E(G_2)| \le 3|V(G_2)|-6$. Od$V(G_1) = V(G_2)$ biorąc pod uwagę, niech $V = V(G_1) = V(G_2)$dla wygody. Potem będzie$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Teraz, dzięki lemacie Handshaking, również to wiemy $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Można więc łatwo zauważyć, że istnieje wierzchołek $v \in V$ takie że $d_{G_1 \cup G_2}(v) < 12\ (*)$. Teraz użyjemy indukcji$|V|$.
Teraz jeśli $|V| = 1$, wynik jest jasny (w rzeczywistości jest jasny $|V| \le 12$). Teraz załóżmy, że indukcyjnie zachodzi to dla grafów planarnych z$|V| = n$. Następnie dla wierzchołka ustawionego za pomocą$|V| = n+1$rozważmy wykres z zestawem wierzchołków $V-v$(Zauważ, że usunięcie wierzchołka nie może sprawić, że planarny wykres stanie się niepłaski). Następnie, dzięki hipotezie indukcyjnej, możemy co najwyżej pokolorować ten wykres$12$zabarwienie. Teraz dodaj$v$z powrotem z usuniętymi krawędziami. Przez$(*)$, $d_{G_1 \cup G_2}(v) < 12$ więc możemy pokolorować ten wierzchołek co najmniej jednym z kolorów użytych na wykresie z ustawionym wierzchołkiem $V-v$ i gotowe.
Wykresy planarne spełniają $|E(G)| \le 3|V(G)|-6$, więc suma dwóch grafów planarnych jest spełniona $|E(G)| \le 6|V(G)|-12$, którego możemy użyć, aby pokazać, że istnieje wierzchołek stopnia mniejszy niż $12$.
To prowadzi nas do dowodu przez indukcję: usuń ten wierzchołek, pokoloruj resztę, a następnie pokoloruj ten wierzchołek. Hipoteza indukcyjna ma zastosowanie, ponieważ każdy podgraf$G$jest również połączeniem dwóch grafów planarnych: odpowiadających im podgrafów$G_1$ i $G_2$.