| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:teo5cores [2023/06/11 14:47] – piva | grafos:teo5cores [2023/06/11 14:49] (atual) – edição externa 127.0.0.1 |
|---|
| |
| Tomando agora $i,j \in \{1,\dots,5\}$, tome $H_{i,j}$ os subgrafos de $G \setminus v$ induzidos. Podemos supor que a componente $C_1$ de $H_{1,3}$ contém $v_1$ e $v_3$. Inclusive, se trocarmos as cores de $1$ e $3$ em todos os vértices de $C_1$, obtemos uma nova $5$-coloração de $G \setminus v$. | Tomando agora $i,j \in \{1,\dots,5\}$, tome $H_{i,j}$ os subgrafos de $G \setminus v$ induzidos. Podemos supor que a componente $C_1$ de $H_{1,3}$ contém $v_1$ e $v_3$. Inclusive, se trocarmos as cores de $1$ e $3$ em todos os vértices de $C_1$, obtemos uma nova $5$-coloração de $G \setminus v$. |
| * Se $v_3 \notin C_1$, então $v_1$ e $v_3$ são ambos coloridos com 3 nessa nova coloração, e podemos então pinta $v$ com a cor 1. | |
| * Assim $H_{1,3}$ contém uma caminho $P$ de $v_1 -- v_3$, como mostrado antes $P$ separa $v_2$ e $v_4$ em $G \setminus v$. | Se $v_3 \notin C_1$, então $v_1$ e $v_3$ são ambos coloridos com $3$ nessa nova coloração, e podemos então pintar $v$ com a cor $1$. Assim $H_{1,3}$ contém uma caminho $P$ de $v_1 - v_3$, como mostrado antes $P$ separa $v_2$ e $v_4$ em $G \setminus v$. Já que $P \cap H_{2,4} = \emptyset$, por isso $v_2$ e $v_4$ estão em faces diferentes de $H_{2,4}$. Na componente contendo $v_2$ , trocamos as cores $2$ e $4$ e trocamos $v_2$ com a cor $4$, assim $v$ não possui vizinhos coloridos com $2$, e podemos colorí-lo com essa cor. |
| * Já que $P \cap H_{2,4} = \emptyset$, por isso $v_2$ e $v_4$ estão em faces diferentes de $H_{2,4}$. | |
| * Na componente contendo $v_2$ , trocamos as cores 2 e 4 e trocamos $v_2$ com a cor 4, assim $v$ não possui vizinhos coloridos com 2, e podemos colorí-lo com essa cor. | |
| |
| <wrap right>$\square$</wrap> | <wrap right>$\square$</wrap> |
| </WRAP> | </WRAP> |