The homomorphism threshold of $\{C_3,C_5\}$-free graphs

Abstract

We determine the structure of $\{C_3,C_5\}$-free graphs with $n$ vertices and minimum degree larger than $n/5$: such graphs are homomorphic to the graph obtained from a $(5k-3)$-cycle by adding all chords of length $1$ mod $5$, for some $k$. This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of $\{C_3,C_5\}$-free graphs is $1/5$, thus answering a question of Oberkampf and Schacht.

30 pages, 13 figures

References in corpus (3)

• Coloring dense graphs via VC-dimension
• On the structure of graphs with given odd girth and large minimum degree
• On the structure of dense graphs with fixed clique number

Cited by in corpus (1)

• On the local density problem for graphs of given odd-girth