The homomorphism threshold of -free graphs.

2019 
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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    17
    References
    2
    Citations
    NaN
    KQI
    []