Combinatorics Seminar

Let F be a fixed family of graphs. The homomorphism threshold of F is the infimum of those α for which there exists an F-free graph H=H(F, α), such that every F-free graph on n vertices of minimum degree αn is homomorphic to H. Letzter and Snyder showed that the homomorphism threshold of the family {C3, C5} is 1/5. They also found explicit graphs H(F, α), for α> 1/5 + ε, which were in addition 3-colourable. Thus, their result also implies that {C3, C5}-free graphs of minimum degree at least (1/5 + ε)n are 3-colourable. For longer cycles, Ebsen and Schacht showed that the homomorphism threshold of {C3, C5, ... , C2k-1} is 1/(2k-1). However, their proof does not imply a good bound on the chromatic number of {C3, C5, ... , C2k-1}-free graphs of minimum degree n/(2k-1). Answering a question of Letzter and Snyder, we prove that such graphs are 3-colourable.