Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph
We prove that for every path H, and every integer d, there is a polynomial f such that every graph G with chromatic number greater than f(t) either contains H as an induced subgraph, or contains as a subgraph the complete d-partite graph with parts of cardinality t. For t = 1 and general d this is a...
| Principais autores: | , , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
Wiley
2024
|