{
  "id": "2212.02737",
  "version": "v1",
  "published": "2022-12-06T04:02:21.000Z",
  "updated": "2022-12-06T04:02:21.000Z",
  "title": "Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs",
  "authors": [
    "Tara Abrishami",
    "Bogdan Alecu",
    "Maria Chudnovsky",
    "Sepehr Hajebi",
    "Sophie Spirkl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let us call a class $\\mathcal{C}$ of graphs clean if for every positive integer $t$ there exists $w(t)$ such that every graph in $\\mathcal{C}$ with treewidth more than $w(t)$ contains an induced subgraph isomorphic to one of the following: the complete graph $K_t$, the complete bipartite graph $K_{t,t}$, a subdivision of the $(t\\times t)$-wall or the line graph of a subdivision of the $(t \\times t)$-wall. In this paper, we use a method due to Lozin and Razgon (building on earlier ideas of Wei{\\ss}auer) in order to characterize the graphs $H$ for which the class of $H$-free graphs is clean. Specifically, this is the case if and only if $H$ is a forest whose components are subdivided stars. Their method (which was used to characterize graphs $H$ whose absence implies bounded treewidth) is readily adapted to yield the above characterization. However, our main result is in fact stronger: we show that forbidding certain connected graphs containing $H$ (rather than $H$ itself) is enough to guarantee cleanness. To obtain this strengthening, we build on a result of Davies and produce a complete description -- of independent interest -- of unavoidable connected induced subgraphs containing $\\eta \\in \\mathbb N$ vertices from a suitably large given set.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-06T04:02:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graphs",
      "basic obstructions",
      "tree-decompositions vii",
      "connected induced subgraphs containing",
      "absence implies bounded treewidth"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}