Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

arXiv2305.15615MaRDI QIDQ6437895FDOQ6437895

Authors: Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl 

Publication date: 24 May 2023

Abstract: The celebrated ErdH{o}s-P'{o}sa Theorem, in one formulation, asserts that for every $cgeq1$, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of $c$ cycles have bounded treewidth. What can we say about the treewidth of graphs containing no induced subgraph isomorphic to the disjoint union of $c$ cycles? Let us call these graphs $c$-perforated. While $1$-perforated graphs have treewidth one, complete graphs and complete bipartite graphs are examples of $2$-perforated graphs with arbitrarily large treewidth. But there are sparse examples, too: Bonamy, Bonnet, D'{e}pr'{e}s, Esperet, Geniet, Hilaire, Thomass'{e} and Wesolek constructed $2$-perforated graphs with arbitrarily large treewidth and no induced subgraph isomorphic to $K_3$ or $K_{3,3}$; we call these graphs occultations. Indeed, it turns out that a mild (and inevitable) adjustment of occultations provides examples of $2$-perforated graphs with arbitrarily large treewidth and arbitrarily large girth, which we refer to as full occultations. Our main result shows that the converse also holds: for every $cgeq1$, a $c$-perforated graph has large treewidth if and only if it contains, as an induced subgraph, either a large complete graph, or a large complete bipartite graph, or a large full occultation. This distinguishes $c$-perforated graphs, among graph classes purely defined by forbidden induced subgraphs, as the first to admit a grid-type theorem incorporating obstructions other than subdivided walls and their line graphs. More generally, for all $c,ogeq1$, we establish a full characterization of induced subgraph obstructions to bounded treewidth in graphs containing no induced subgraph isomorphic to the disjoint union of $c$ cycles, each of length at least $o+2$.

This page was built for publication: Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437895)