Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656708 | Journal of Combinatorial Theory, Series B | 2016 | 20 Pages |
Abstract
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 ℓ.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maria Chudnovsky, Alex Scott, Paul Seymour,