| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:teoerdos [2023/06/12 14:00] – piva | grafos:teoerdos [2023/06/12 14:15] (atual) – edição externa 127.0.0.1 |
|---|
| Como $G$ não é um grafo multipartido completo, a não-adjacência não é uma relação equivalente em $V(G)$. Portanto, existem vértices $y_1,x,y_2$ tais que $y_1x,xy_2 \notin E(G)$, mas $y_1y_2 \in E(G)$. Como $G$ é aresta-máximal sem um subgrafo $k$-construtível, cada aresta $xy_i$ está em algum subgrafo $k$-construtível $H_i$ de $G+xy_i (i=1,2)$. | Como $G$ não é um grafo multipartido completo, a não-adjacência não é uma relação equivalente em $V(G)$. Portanto, existem vértices $y_1,x,y_2$ tais que $y_1x,xy_2 \notin E(G)$, mas $y_1y_2 \in E(G)$. Como $G$ é aresta-máximal sem um subgrafo $k$-construtível, cada aresta $xy_i$ está em algum subgrafo $k$-construtível $H_i$ de $G+xy_i (i=1,2)$. |
| |
| Seja H uma cópia isomórfica de H que contém X e H, mas é disjunta de G, junto com um isomorfismo V de H para H que faz H ponto a ponto. Então H, então H é $k$-contrutível por $(iii)$. Um vértice de cada vez, identifiquemos em H cada vértice V com seu parceiro V; como V nunca é uma aresta de H, cada uma dessas identificações equivale a uma etapa de construção do tipo (ii). Eventualmente, obtemos o grafo H; este é o subgrafo K-construtível desejado de G. | Seja $H_2'$ uma cópia isomórfica de $H_2$ que contém $x$ e $H_2-H_1$, mas é disjunta de $G$, junto com um isomorfismo $v \mapsto v'$ de $H_2$ para $H_2'$ que fixa $H_2 \cap H_2'$ ponto a ponto. Então $H_1 \cap H_2' = \{x\}$, então |
| | |
| | $$H := (H_1 \cup H_2')-xy_1-xy_2' +y_1y_2'$$ |
| | |
| | é $k$-contrutível por $(iii)$. Um vértice de cada vez, identifiquemos em $H$ cada vértice $v' \in H_2'-G$ com seu parceiro $v$; como $vv'$ nunca é uma aresta de $H$, cada uma dessas identificações equivale a uma etapa de construção do tipo $(ii)$. Eventualmente, obtemos o grafo |
| | |
| | $$(H_1 \cup H_2) -xy_1-xy_2+y_1y_2 \subseteq G;$$ |
| | |
| | este é o subgrafo $k$-construtível desejado de $G$. |
| </WRAP> | </WRAP> |
| |
| ---- | ---- |
| |
| O teorema de Hajós resolve nosso problema do tipo Kuratowski para grafos altamente cromáticos, que era encontrar uma classe de grafos de número cromático pelo menos K com a propriedade de que todo grafo tem subgrafo nessa classe? Formalmente, sim, embora com uma classe de caracterização infinita (a classe de grafos K-construtíveis) que contém X adequadamente.Ao contrário da caracterização de grafos planares de Kuratowski, no entanto, isso não torna, pelo menos não obviamente, o teorema de Hajó uma boa caracterização dos grafos do número cromático K: como se pode mostrar, provando que um determinado grafo K-construtível é de fato K-construtível é tão difícil quanto provar que um gráfico de número cromático K realmente precisa de pelo menos K cores. Consulte a nota para obter detalhes. | O teorema de Hajós resolve nosso problema do tipo Kuratowski para grafos altamente cromáticos, que era encontrar uma classe de grafos de número cromático pelo menos $k$ com a propriedade de que todo grafo tem subgrafo nessa classe? Formalmente, sim, embora com uma classe de caracterização infinita (a classe de grafos K-construtíveis) que contém $\mathcal{X}_k$ adequadamente. Ao contrário da caracterização de grafos planares de Kuratowski, no entanto, isso não torna, pelo menos não obviamente, o teorema de Hajó uma boa caracterização dos grafos do número cromático $<k$: como se pode mostrar, provando que um determinado grafo $k$-construtível é de fato $k$-construtível é tão difícil quanto provar que um gráfico de número cromático $\geq k$ realmente precisa de pelo menos $k$ cores. **Consulte a nota para obter detalhes.*** |
| | |
| | ---- |
| | |
| | <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. 125-127. Acesso em 10/06/2023. |
| | |
| | </WRAP> |