{
  "id": "0906.4142",
  "version": "v3",
  "published": "2009-06-22T23:01:30.000Z",
  "updated": "2011-03-30T21:19:03.000Z",
  "title": "The maximum number of cliques in a graph embedded in a surface",
  "authors": [
    "Vida Dujmović",
    "Gašper Fijavž",
    "Gwenaël Joret",
    "Thom Sulanke",
    "David R. Wood"
  ],
  "journal": "European J. Combinatorics 32.8:1244-1252, 2011",
  "doi": "10.1016/j.ejc.2011.04.001",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper studies the following question: Given a surface $\\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\\Sigma$? We characterise the extremal graphs for this question, and prove that the answer is between $8(n-\\omega)+2^{\\omega}$ and $8n+{3/2} 2^{\\omega}+o(2^{\\omega})$, where $\\omega$ is the maximum integer such that the complete graph $K_\\omega$ embeds in $\\Sigma$. For the surfaces $\\mathbb{S}_0$, $\\mathbb{S}_1$, $\\mathbb{S}_2$, $\\mathbb{N}_1$, $\\mathbb{N}_2$, $\\mathbb{N}_3$ and $\\mathbb{N}_4$ we establish an exact answer.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2011-03-30T21:19:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C35"
    ],
    "keywords": [
      "maximum number",
      "exact answer",
      "complete graph",
      "paper studies"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.4142D"
    }
  }
}