{
  "id": "1404.4987",
  "version": "v1",
  "published": "2014-04-19T21:25:45.000Z",
  "updated": "2014-04-19T21:25:45.000Z",
  "title": "Between 2- and 3-colorability",
  "authors": [
    "Alan Frieze",
    "Wesley Pegden"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n,\\,1<c\\leq 4$. We show that for any positive integer $\\ell$, there exists $\\epsilon=\\epsilon(\\ell)$ such that if $c=1+\\epsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\\ell+1}$ so long as its odd-girth is at least $2\\ell+1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\\chi(G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-19T21:25:45.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "homomorphism",
      "odd cycles",
      "positive integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.4987F"
    }
  }
}