L'union de deux graphes planaires simples a un nombre chromatique $\leq 12$

Dec 16 2020

Considérons le graphique $G$étant l'union de deux graphes planaires simples tous deux sur le même ensemble de sommets. Je veux montrer$\chi(G) \leq 12$.

Le théorème des quatre couleurs indique que le nombre chromatique d'un graphe plan est inférieur à 4, et pour les graphes généraux $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Mais cela ne donnerait qu'une limite supérieure de 16. Y a-t-il quelque chose de particulier au graphique planaire qui aide à réduire la limite?

Réponses

1 ArsenBerk Dec 15 2020 at 23:50

Puisque $G_1$ et $G_2$ sont planaires, nous avons $|E(G_1)| \le 3|V(G_1)|-6$ et $|E(G_2)| \le 3|V(G_2)|-6$. Puisque$V(G_1) = V(G_2)$ donné, laissez $V = V(G_1) = V(G_2)$pour plus de commodité. Ensuite nous avons$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Maintenant, par le lemme de poignée de main, nous savons aussi que $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Ainsi, on peut facilement voir qu'il existe un sommet $v \in V$ tel que $d_{G_1 \cup G_2}(v) < 12\ (*)$. Maintenant, nous allons utiliser l'induction sur$|V|$.

Maintenant si $|V| = 1$, le résultat est clair (en fait c'est clair pour $|V| \le 12$). Maintenant, supposons que cela soit inductif pour les graphes planaires avec$|V| = n$. Ensuite, pour un ensemble de sommets avec$|V| = n+1$, considérons un graphe avec un ensemble de sommets $V-v$(Notez que la suppression d'un sommet ne peut pas rendre un graphe plan non planaire). Ensuite, par hypothèse d'induction, nous pouvons colorier ce graphique avec au plus$12$couleurs. Maintenant, ajoutez$v$retour avec les bords supprimés. Par$(*)$, $d_{G_1 \cup G_2}(v) < 12$ afin que nous puissions colorer ce sommet avec au moins une des couleurs utilisées dans le graphique avec l'ensemble de sommets $V-v$ et nous avons terminé.

2 MishaLavrov Dec 15 2020 at 23:42

Les graphes planaires satisfont $|E(G)| \le 3|V(G)|-6$, donc l'union de deux graphes planaires satisfait $|E(G)| \le 6|V(G)|-12$, que nous pouvons utiliser pour montrer qu'il existe un sommet de degré inférieur à $12$.

Cela nous conduit à une preuve par induction: supprimez ce sommet, colorez le reste, puis colorez ce sommet. L'hypothèse inductive s'applique parce que tout sous-graphe de$G$est également une union de deux graphes planaires: les sous-graphes correspondants de$G_1$ et $G_2$.