| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:teoerdos [2023/06/12 14:07] – edição externa 127.0.0.1 | grafos:teoerdos [2023/06/12 14:15] (atual) – edição externa 127.0.0.1 |
|---|
| $$H := (H_1 \cup H_2')-xy_1-xy_2' +y_1y_2'$$ | $$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 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. | é $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> |