{
  "id": "2203.06775",
  "version": "v1",
  "published": "2022-03-13T22:01:16.000Z",
  "updated": "2022-03-13T22:01:16.000Z",
  "title": "Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs",
  "authors": [
    "Tara Abrishami",
    "Maria Chudnovsky",
    "Sepehr Hajebi",
    "Sophie Spirkl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A hole in a graph $G$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $K_4$ by removing an edge. A pyramid is a graph consisting of a triangle called the base, a vertex called the apex, and three internally disjoint paths starting at the apex and disjoint otherwise, each joining the apex to a vertex of the base. For a family $\\mathcal{H}$ of graphs, we say a graph $G$ is $\\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\\mathcal{H}$. Cameron, da Silva, Huang, and Vu\\v{s}kovi\\'c proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, $K_4$)-free graphs of arbitrarily large treewidth, and observing induced diamonds all over their construction, they conjectured that (even hole, diamond, $K_4$)-free graphs have bounded treewidth. We approach this conjecture by showing that for every $t$, (even hole, pyramid, diamond, $K_t$)-free graphs have bounded treewidth. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses \"non-crossing decompositions\" methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of \"non-crossing decompositions\" to prove bounded treewidth in a graph class of unbounded maximum degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-03-13T22:01:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "induced subgraph",
      "tree decompositions",
      "bounded treewidth",
      "free graphs",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}