Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:teoerdos [2023/06/12 14:08] – piva | grafos:teoerdos [2023/06/12 14:15] (atual) – edição externa 127.0.0.1 |
|---|
| ---- | ---- |
| |
| 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> |