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
|
| Summary: | 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 hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ. |
|---|