두 개의 단순 평면 그래프의 합집합은 색수를가집니다. $\leq 12$

Dec 16 2020

그래프 고려 $G$동일한 정점 세트에있는 두 개의 단순 평면 그래프의 합집합입니다. 나는 보여주고 싶다$\chi(G) \leq 12$.

네 가지 색 정리는 평면 그래프의 색 수가 4 미만임을 나타내며 일반 그래프의 경우 $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. 그러나 이것은 16의 상한을 산출합니다. 경계를 줄이는 데 도움이되는 평면형 그래프에 특별한 것이 있습니까?

답변

1 ArsenBerk Dec 15 2020 at 23:50

이후 $G_1$$G_2$ 평면, 우리는 $|E(G_1)| \le 3|V(G_1)|-6$$|E(G_2)| \le 3|V(G_2)|-6$. 이후$V(G_1) = V(G_2)$ 주어진,하자 $V = V(G_1) = V(G_2)$편의상. 그런 다음 우리는$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ 이제 Handshaking Lemma를 통해 $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ 따라서 정점이 존재한다는 것을 쉽게 알 수 있습니다. $v \in V$ 그런 $d_{G_1 \cup G_2}(v) < 12\ (*)$. 이제 우리는$|V|$.

자, 만약 $|V| = 1$, 결과는 분명합니다 (실제로 $|V| \le 12$). 이제 귀납적으로 평면 그래프를 유지한다고 가정합니다.$|V| = n$. 그런 다음 정점 세트에 대해$|V| = n+1$, 정점이 설정된 그래프를 고려하십시오. $V-v$(정점을 제거하면 평면 그래프가 비평면이 될 수 없습니다.) 그런 다음 귀납 가설에 의해이 그래프를 최대$12$그림 물감. 이제 추가$v$제거 된 가장자리와 함께 다시. 으로$(*)$, $d_{G_1 \cup G_2}(v) < 12$ 그래서 우리는 꼭지점이 설정된 그래프에 사용 된 적어도 하나의 색으로이 꼭지점을 채색 할 수 있습니다. $V-v$ 그리고 우리는 끝났습니다.

2 MishaLavrov Dec 15 2020 at 23:42

평면 그래프는 $|E(G)| \le 3|V(G)|-6$이므로 두 평면 그래프의 합집합은 다음을 충족합니다. $|E(G)| \le 6|V(G)|-12$, 이보다 작은 정도의 정점이 있음을 표시하는 데 사용할 수 있습니다. $12$.

이것은 귀납법에 의한 증명으로 이어집니다. 그 정점을 제거하고 나머지를 채색 한 다음 그 정점을 채색합니다. 귀납적 가설이 적용되는 이유는$G$이며 또한 두 평면 그래프의 연합 : 서브 그래프의 대응$G_1$$G_2$.