Browsing by Author "Spirkl, Sophie"

Now showing 1 - 4 of 4

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.
Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path.
(Springer, 2023-09-15) Scott, Alex; Seymour, Paul; Spirkl, Sophie
A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5-free graph with clique number ω ≥ 3 has chromatic number at most ωlog2(ω). The best previous result was an exponential upper bound (5/27)3ω, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erd˝os-Hajnal conjecture holds for P5, which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5-free graphs, and our result is an attempt to approach that.
Pure Pairs. VIII. Excluding a Sparse Graph.
(Springer, 2024-08-05) Scott, Alex; Seymour, Paul; Spirkl, Sophie
A pure pair of size t in a graph G is a pair A, B of disjoint subsets of V(G), each of cardinality at least t, such that A is either complete or anticomplete to B. It is known that, for every forest H, every graph on n ≥ 2 vertices that does not contain H or its complement as an induced subgraph has a pure pair of size (n); furthermore, this only holds when H or its complement is a forest. In this paper, we look at pure pairs of size n1−c, where 0 < c < 1. Let H be a graph: does every graph on n ≥ 2 vertices that does not contain H or its complement as an induced subgraph have a pure pair of size (|G| 1−c)? The answer is related to the congestion of H, the maximum of 1 − (|J | − 1)/|E(J )| over all subgraphs J of H with an edge. (Congestion is nonnegative, and equals zero exactly when H is a forest.) Let d be the smaller of the congestions of H and H. We show that the answer to the question above is “yes” if d ≤ c/(9 + 15c), and “no” if d > c.