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...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
Elsevier
2016
|