| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:colouringintro [2023/05/08 21:52] – edição externa 127.0.0.1 | grafos:colouringintro [2023/06/11 14:03] (atual) – edição externa 127.0.0.1 |
|---|
| $$d(G) = 2m / n \leq 2(3n-6) / n <6;$$ | $$d(G) = 2m / n \leq 2(3n-6) / n <6;$$ |
| |
| seja $v \in G$ um vértice de grau no máximo $5$. Pela hipótese de indução, o grafo $H := G-v$ tem uma coloração de vértice $\mathcal{c} : V(H) \to \{1, \dots\5\}$. Se $\mathcal{c}$ usa no máximo $4$ cores para os vizinhos de $v$, podemos estendê-lo para uma $5$-coloração de $G$. Suponhamos, portanto, que $v$ tenha exatamente $5$ vizinhos, e que estes tenham cores distintas. | seja $v \in G$ um vértice de grau no máximo $5$. Pela hipótese de indução, o grafo $H := G-v$ tem uma coloração de vértice $\mathcal{c} : V(H) \to \{1, \dots ,5\}$. Se $\mathcal{c}$ usa no máximo $4$ cores para os vizinhos de $v$, podemos estendê-lo para uma $5$-coloração de $G$. Suponhamos, portanto, que $v$ tenha exatamente $5$ vizinhos, e que estes tenham cores distintas. |
| |
| Seja $D$ um disco aberto em torno de $v$, tão pequeno que encontre apenas aqueles cinco segmentos de borda reta de $G$ que contém $v$. Vamos enumerar esses segmentos de acordo com sua posição cíclica em $D$ como $s_1, \dots, s_5$, e seja $vv_{i}$ a aresta que contém $s_{i} (i=1, \dots ,5)$. Sem perda de generalidade, podemos assumir que $\mathcal{c}(v_{i}) = i$ para cada $i$. | Seja $D$ um disco aberto em torno de $v$, tão pequeno que encontre apenas aqueles cinco segmentos de borda reta de $G$ que contém $v$. Vamos enumerar esses segmentos de acordo com sua posição cíclica em $D$ como $s_1, \dots, s_5$, e seja $vv_{i}$ a aresta que contém $s_{i} (i=1, \dots ,5)$. Sem perda de generalidade, podemos assumir que $\mathcal{c}(v_{i}) = i$ para cada $i$. |
| |
| (FIGURAAAAAA | {{ :grafos:graph501.png?400 |}} |
| |
| Vamos mostrar primeiro que todo V caminho P separa V de V em H. Claramente, este é o caso se e somente se o ciclo C separa V de V em G. Provamos isso mostrando que V e V estão em faces diferentes de C. | Vamos mostrar primeiro que todo $v_1-v_3$ caminho $P \subseteq H-\{v_2,v_4\}$ separa $v_2$ de $v_4$ em $H$. Claramente, este é o caso se, e somente se, o ciclo $C := vv_{1}Pv_{3}v$ separa $v_2$ de $v_4$ em $G$. Provamos isso mostrando que $v_2$ e $v_4$ estão em faces diferentes de $C$. |
| |
| Vamos pegar um ponto interno X de S em D e um ponto interno X de S em D. Então, em D, todo ponto pode ser ligado por um arco poligonal a X ou a X. Isso implica que X e X (e, portanto, também V e V) estão em diferentes faces de C: caso contrário, D encontraria apenas uma das duas faces de C, o que contradiria o fato de que V está na quarta face de ambas as faces (Teorema 4.1.1). | Vamos pegar um ponto interno $x_2$ de $s_2$ em $D$ e um ponto interno $x_4$ de $s_4$ em $D$. Então, em $D \setminus (s_1 \cup s_3) \subseteq \mathbb{R}^2 \setminus C$ todo ponto pode ser ligado por um arco poligonal a $x_2$ ou a $x_4$. Isso implica que $x_24 e $x_4$ (e, portanto, também $v_2$ e $v_4$) estão em diferentes faces de $C$: caso contrário, $D$ encontraria apenas uma das duas faces de $C$, o que contradiria o fato de que $v$ está na fronteira de ambas as faces **(Teorema 4.1.1)**. |
| |
| Dado J, seja H o subgrafo de H induzido pelos vértices coloridos J ou J. Podemos assumir que a componente C de H contendo V também contém V. De fato, se trocarmos as cores 1 e 3 em todos os vértices de C , obtemos outra 5-coloração de H; se V , então V e V são ambos coloridos 3 nesta nova coloração, e podemos atribuir a cor 1 a V. Assim, H contém um V caminho P. Como mostrado acima, P separa V de V em H. Como P, isso significa que V e V estão em componentes diferentes de H. No componente que contém V, agora trocamos as cores 2 e 4, recolorindo assim V com a cor 4. Agora V não tem mais um vizinho colorido 2, e podemos dar a ele esta cor. | Dado $i,j \in \{1, \dots ,5\}$, seja $H_{i,j}$ o subgrafo de $H$ induzido pelos vértices coloridos $i$ ou $j$. Podemos assumir que a componente $C_1$ de $H_{1,3}$ contendo $v_1$ também contém $v_3$. De fato, se trocarmos as cores $1$ e $3$ em todos os vértices de $C_1$ , obtemos outra $5$-coloração de $H$; se $v_3 \notin C_1$ , então $v_1$ e $v_3$ são ambos coloridos $3$ nesta nova coloração, e podemos atribuir a cor $1$ a $v$. Assim, $H_{1,3}$ contém um $v_1-v_3$ caminho $P$. Como mostrado acima, $P$ separa $v_2$ de $v_44 em $H$. Como $P \cap H_{2,4} = \emptyset$, isso significa que $v_2$ e $v_4$ estão em componentes diferentes de $H_{2,4}$. No componente que contém $v_2$, agora trocamos as cores $2$ e $4$, recolorindo assim $v_2$ com a cor $4$. Agora $v$ não tem mais um vizinho colorido $2$, e podemos dar a ele esta cor. |
| </WRAP> | </WRAP> |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| === Teorema de Grotzsch (1959) === | === Teorema de Grotzsch (1959) === |
| Todo grafo planar que não contém um triângulo é 3-colorível. | //Todo grafo planar que não contém um triângulo é $3$-colorível.// |
| | </WRAP> |
| | |
| | ---- |
| | |
| | <WRAP round info 100%> |
| | === Referências === |
| | * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 119-121. Acesso em 10/06/2023. |
| </WRAP> | </WRAP> |