Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd ho...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2016
|