{
  "id": "2103.00882",
  "version": "v1",
  "published": "2021-03-01T10:07:46.000Z",
  "updated": "2021-03-01T10:07:46.000Z",
  "title": "k-apices of minor-closed graph classes. I. Bounding the obstructions",
  "authors": [
    "Ignasi Sau",
    "Giannos Stamoulis",
    "Dimitrios M. Thilikos"
  ],
  "comment": "46 pages and 12 figures. arXiv admin note: text overlap with arXiv:2004.12692",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "abstract": "Let ${\\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of ${\\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\\setminus S$ belongs to ${\\cal G}.$ We denote by ${\\cal A}_k ({\\cal G})$ the set of all graphs that are $k$-apices of ${\\cal G}.$ We prove that every graph in the obstruction set of ${\\cal A}_k ({\\cal G}),$ i.e., the minor-minimal set of graphs not belonging to ${\\cal A}_k ({\\cal G}),$ has size at most $2^{2^{2^{2^{{\\sf poly}(k)}}}},$ where ${\\sf poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of ${\\cal G}.$ This bound drops to $2^{2^{{\\sf poly}(k)}}$ when ${\\cal G}$ excludes some apex graph as a minor.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-01T10:07:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C83",
      "05C75",
      "05C69",
      "G.2.2",
      "F.2.2"
    ],
    "keywords": [
      "minor-closed graph class",
      "bound drops",
      "polynomial function",
      "minor-minimal set",
      "apex graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 46,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}