Browsing by Author "Hajebi, Sepehr"

Now showing 1 - 3 of 3

Foreshadowing the Grid Theorem for Induced Subgraphs
(University of Waterloo, 2024-08-07) Hajebi, Sepehr
We prove several dichotomy theorems toward a complete description of the unavoidable induced subgraphs of graphs with large treewidth. This is motivated by the Grid Theorem of Robertson and Seymour (1986) which achieves the same goal for minors (and subgraphs). Given a graph class C, we say that C is clean if the only induced subgraph obstructions to bounded treewidth in C are the basic ones: complete graphs, complete bipartite graphs, subdivided walls and the line graphs of the subdivided walls. The analog of the Grid Theorem for induced subgraphs (still out of reach) is then observed to be equivalent to a characterization of all hereditary classes that are clean. We characterize all clean classes that are defined by finitely many excluded induced subgraphs. Specifically, we identify a family of “non-basic” obstructions which, in this scenario, litmus-test the clean classes against the non-clean ones. The analogous characterization remains elusive in the case of infinitely many forbidden induced subgraphs. Among the infinite sets of graphs whose exclusion is known to result in a non-clean class, the following four appear to expose a distinctive gap in our understanding of cleanness: (1) Graphs which are the union of three cycles, all sharing a vertex and otherwise pairwise vertex-disjoint. (2) Graphs which are the union of two vertex-disjoint cycles. (3) Graphs consisting of two non-adjacent vertices with three pairwise internally disjoint paths between them, known as thetas. (4) Cycles with an even number of vertices (at least four), known as even holes. For i = 1, 2, 3, 4, let Ci be the class obtained by excluding the ith set above. We prove a full “grid-type theorem” for each of C1 and C2. Both results extend to an arbitrary number of excluded cycles (instead of “three” and “two”) of lower bounded lengths. In C3 and C4, we characterize the “local” structure of graphs with large treewidth. Explicitly, given a graph H, we prove the following: (a) Every (theta, K3)-free graph of large enough treewidth has an induced subgraph isomorphic to H, if and only if H is a K3-free chordal graph (that is, a forest). (b) Every (even hole K4)-free graph of large enough treewidth has an induced subgraph isomorphic to H, if and only if H is a K4-free chordal graph. We generalize both (a) and (b) to the “right” class of Kt-free graphs for all t. We also derive, from a very special case of (b), one of the two conjectures of Sintiari and Trotignon on even-hole-free graphs of large treewidth.
Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
(Elsevier, 2025-01) Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie
This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph t-clean if it does not contain as an induced subgraph the complete graph Kt, the complete bipartite graph Kt,t, subdivisions of a (t x t)-wall, and line graphs of subdivisions of a (t x t)-wall. It is known that graphs with bounded treewidth must be t-clean for some t; however, it is not true that every t-clean graph has bounded treewidth. In this paper, we show that three types of cutsets, namely clique cutsets, 2-cutsets, and 1-joins, interact well with treewidth and with each other, so graphs that are decomposable by these cutsets into basic classes of bounded treewidth have bounded treewidth. We apply this result to two hereditary graph classes, the class of (ISK4, well)-free graphs and the class of graphs with no cycle with a unique chord. These classes were previously studied and decomposition theorems were obtained for both classes. Our main results are that t-clean (ISK4, wheel)-free graphs have bounded treewidth and that t-clean graphs with no cycle with a unique chord have bounded treewidth.
Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole.
(Elsevier, 2025-02) Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie
A clock is a graph consisting of an induced cycle C and a vertex not in C with at least two non-adjacent neighbours in C. We show that every clock-free graph of large treewidth contains a "basic obstruction" of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.