pith. sign in

arxiv: 1610.04932 · v3 · pith:RQ6BSKPLnew · submitted 2016-10-17 · 🧮 math.CO

The homomorphism threshold of \{C₃, C₅\}-free graphs

classification 🧮 math.CO
keywords graphsfreehomomorphismquestionschachtthresholdaddinganswering
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.