TY - JOUR

T1 - Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Hajebi, Sepehr

AU - Spirkl, Sophie

N1 - Funding Information:
†We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912].
Funding Information:
Supported by NSF Grant DMS-1763817 and NSF-EPSRC Grant DMS-2120644. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020- 03912].
Funding Information:
∗Supported by NSF Grant DMS-1763817 and NSF-EPSRC Grant DMS-2120644.
Publisher Copyright:
© The authors.

PY - 2023

Y1 - 2023

N2 - 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 K4 by removing an edge. A pyramid is a graph consisting of a vertex a called the apex and a triangle {b1, b2, b3} called the base, and three paths Pi from a to bi for(formal present)all of length at least one, such that for i ∕= j, the only edge between Pi \ {a} and Pj \ {a} is bibj, and at most one of P1, P2, and P3 has length exactly one. For a family H of graphs, we say a graph G is H-free if no induced subgraph of G is isomorphic to a member of H. Cameron, da Silva, Huang, and Vušković 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, pyramid, K4)-free graphs of arbitrarily large treewidth. Here, we show that for every t, (even hole, pyramid, diamond, Kt)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. 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.

AB - 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 K4 by removing an edge. A pyramid is a graph consisting of a vertex a called the apex and a triangle {b1, b2, b3} called the base, and three paths Pi from a to bi for(formal present)all of length at least one, such that for i ∕= j, the only edge between Pi \ {a} and Pj \ {a} is bibj, and at most one of P1, P2, and P3 has length exactly one. For a family H of graphs, we say a graph G is H-free if no induced subgraph of G is isomorphic to a member of H. Cameron, da Silva, Huang, and Vušković 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, pyramid, K4)-free graphs of arbitrarily large treewidth. Here, we show that for every t, (even hole, pyramid, diamond, Kt)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. 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.

UR - http://www.scopus.com/inward/record.url?scp=85162971061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85162971061&partnerID=8YFLogxK

U2 - 10.37236/11623

DO - 10.37236/11623

M3 - Article

AN - SCOPUS:85162971061

SN - 1077-8926

VL - 30

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - P2.42

ER -