Abstract
Consider a family of -free graphs, where . Suppose that each graph in has minimum degree linear in its number of vertices. Thomassen showed that such a family has bounded chromatic number, or, equivalently, that all graphs in are homomorphic to a complete graph of bounded size. Considering instead homomorphic images which are themselves -free, we construct a family of dense -free graphs with no -free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of odd cycles of length at least 5 and answers a question of Ebsen and Schacht. Our proof introduces a new technique to describe the topological structure of a graph. We establish a graph-theoretic analogue of homotopy equivalence, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has unexpected connections to the neighborhood complex, leading to multiple interesting questions.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.