{
  "id": "1910.04609",
  "version": "v1",
  "published": "2019-10-10T14:40:26.000Z",
  "updated": "2019-10-10T14:40:26.000Z",
  "title": "Small families under subdivision",
  "authors": [
    "Maria Chudnovsky",
    "Martin Loebl",
    "Paul Seymour"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $H$ be a graph with maximum degree $d$, and let $d'\\ge 0$. We show that for some $c>0$ depending on $H,d'$, and all integers $n\\ge 0$, there are at most $c^n$ unlabelled simple $d$-connected $n$-vertex graphs with maximum degree at most $d'$ that do not contain $H$ as a subdivision. On the other hand, the number of unlabelled simple $(d-1)$-connected $n$-vertex graphs with minimum degree $d$ and maximum degree at most $d+1$ that do not contain $K_{d+1}$ as a subdivision is superexponential in $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-10T14:40:26.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "small families",
      "subdivision",
      "maximum degree",
      "vertex graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}