{
  "id": "1610.04932",
  "version": "v1",
  "published": "2016-10-17T00:09:42.000Z",
  "updated": "2016-10-17T00:09:42.000Z",
  "title": "The homomorphism threshold of $\\{C_3, C_5\\}$-free graphs",
  "authors": [
    "Shoham Letzter",
    "Richard Snyder"
  ],
  "comment": "33 pages, 21 figures",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-17T00:09:42.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graphs",
      "homomorphism threshold",
      "minimum degree larger",
      "homomorphic"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}