{
  "id": "1312.6213",
  "version": "v2",
  "published": "2013-12-21T06:44:49.000Z",
  "updated": "2014-11-15T22:05:42.000Z",
  "title": "Subdivisions of a large clique in $C_6$-free graphs",
  "authors": [
    "József Balogh",
    "Hong Liu",
    "Maryam Sharifzadeh"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Mader conjectured that every $C_4$-free graph has a subdivision of a clique of order linear in its average degree. We show that every $C_6$-free graph has such a subdivision of a large clique. We also prove the dense case of Mader's conjecture in a stronger sense, i.e. for every $c$, there is a $c'$ such that every $C_4$-free graph with average degree $cn^{1/2}$ has a subdivision of a clique $K_\\ell$ with $\\ell=\\lfloor c'n^{1/2}\\rfloor$ where every edge is subdivided exactly $3$ times.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-21T06:44:49.000Z",
      "comment": "15 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-11-15T22:05:42.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "large clique",
      "subdivision",
      "average degree",
      "dense case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.6213B"
    }
  }
}