Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie

doi:10.5802/igt.6

Alecu, Bogdan ¹; Chudnovsky, Maria ²; Hajebi, Sepehr ³; Spirkl, Sophie ³

¹ School of Computing, University of Leeds, Leeds, UK.
² Princeton University, Princeton, NJ, USA
³ Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada

Innovations in Graph Theory, Volume 2 (2025), pp. 1-23.

Abstract

Given $c \in ℕ$ , we say a graph $G$ is $c$ -pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of $c$ -pinched graphs?

For instance, $1$ -pinched graphs are exactly graphs of treewidth $1$ . However, bounded treewidth for $c > 1$ is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of $2$ -pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of $c$ , discovered by Pohoata and later independently by Davies, consisting of $3$ -pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions.

We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every $c \in ℕ$ , a $c$ -pinched graph $G$ has large treewidth if and only if $G$ contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata–Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded.

Received: 2023-09-21
Accepted: 2025-02-12
Published online: 2025-02-13

DOI: 10.5802/igt.6

Classification: 05C75, 05C83
Mots-clés : Induced subgraphs, Treewidth, Graph minors, Grid theorem

Author's affiliations:

Alecu, Bogdan ¹; Chudnovsky, Maria ²; Hajebi, Sepehr ³; Spirkl, Sophie ³

¹ School of Computing, University of Leeds, Leeds, UK.
² Princeton University, Princeton, NJ, USA
³ Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{IGT_2025__2__1_0,
     author = {Alecu, Bogdan and Chudnovsky, Maria and Hajebi, Sepehr and Spirkl, Sophie},
     title = {Induced subgraphs and tree decompositions {XII.} {Grid} theorem for pinched graphs},
     journal = {Innovations in Graph Theory},
     pages = {1--23},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     doi = {10.5802/igt.6},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.6/}
}

TY  - JOUR
AU  - Alecu, Bogdan
AU  - Chudnovsky, Maria
AU  - Hajebi, Sepehr
AU  - Spirkl, Sophie
TI  - Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 1
EP  - 23
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.6/
DO  - 10.5802/igt.6
LA  - en
ID  - IGT_2025__2__1_0
ER  -

%0 Journal Article
%A Alecu, Bogdan
%A Chudnovsky, Maria
%A Hajebi, Sepehr
%A Spirkl, Sophie
%T Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
%J Innovations in Graph Theory
%D 2025
%P 1-23
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.6/
%R 10.5802/igt.6
%G en
%F IGT_2025__2__1_0

Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie. Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs. Innovations in Graph Theory, Volume 2 (2025), pp. 1-23. doi : 10.5802/igt.6. https://igt.centre-mersenne.org/articles/10.5802/igt.6/

References
Cited by

[1] Aboulker, Pierre; Adler, Isolde; Kim, Eun Jung; Sintiari, Ni Luh Dewi; Trotignon, Nicolas On the tree-width of even-hole-free graphs, Eur. J. Comb., Volume 98 (2021), Paper no. 103394, 21 pages | DOI | MR | Zbl

[2] Abrishami, Tara; Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie Induced subgraphs and tree decompositions VII. Basic obstructions in $H$ -free graphs, J. Comb. Theory, Ser. B, Volume 164 (2024), pp. 443-472 | DOI | MR | Zbl

[3] Abrishami, Tara; Chudnovsky, Maria; Dibek, Cemil; Hajebi, Sepehr; Rzążewski, Paweł; Spirkl, Sophie; Vušković, Kristina Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree, J. Comb. Theory, Ser. B, Volume 164 (2024), pp. 371-403 | DOI | MR | Zbl

[4] Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie Induced subgraphs and tree decompositions IX. Grid Theorem for perforated graphs (2023) | arXiv

[5] Bodlaender, Hans L. Dynamic programming on graphs with bounded treewidth, Automata, languages and programming (Tampere, 1988) (Lecture Notes in Computer Science), Volume 317, Springer, 1988, pp. 105-118 | DOI | MR | Zbl

[6] Bonamy, Marthe; Bonnet, Édouard; Déprés, Hugues; Esperet, Louis; Geniet, Colin; Hilaire, Claire; Thomassé, Stéphan; Wesolek, Alexandra Sparse graphs with bounded induced cycle packing number have logarithmic treewidth, J. Comb. Theory, Ser. B, Volume 167 (2024), pp. 215-249 | DOI | MR | Zbl

[7] Davies, James Graph Theory workshop in Oberwolfach, Oberwolfach Rep., Volume 19 (2022) no. 1, pp. 5-78 https://ems.press/journals/owr/articles/9790352 | DOI

[8] Dvořák, Zdeněk Induced subdivisions and bounded expansion, Eur. J. Comb., Volume 69 (2018), pp. 143-148 | DOI | MR | Zbl

[9] Hajebi, Sepehr; Li, Yanjia; Spirkl, Sophie Hitting all maximum stable sets in $P_{5}$ -free graphs, J. Comb. Theory, Ser. B, Volume 165 (2024), pp. 142-163 | DOI | MR | Zbl

[10] Hickingbotham, Robert; Illingworth, Freddie; Mohar, Bojan; Wood, David R. Treewidth, circle graphs, and circular drawings, SIAM J. Discrete Math., Volume 38 (2024) no. 1, pp. 965-987 | DOI | MR

[11] Korhonen, Tuukka Grid induced minor theorem for graphs of small degree, J. Comb. Theory, Ser. B, Volume 160 (2023), pp. 206-214 | DOI | MR | Zbl

[12] Lozin, Vadim; Razgon, Igor Tree-width dichotomy, Eur. J. Comb., Volume 103 (2022), Paper no. 103517, 8 pages | DOI | MR | Zbl

[13] Pohoata, Cosmin Unavoidable induced subgraphs of large graphs (2014) (Senior thesis, Princeton University)

[14] Ramsey, Frank P. On a Problem of Formal Logic, Proc. Lond. Math. Soc. (2), Volume 30 (1929) no. 4, pp. 264-286 | DOI | MR | Zbl

[15] Robertson, Neil; Seymour, Paul Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B, Volume 41 (1986) no. 1, pp. 92-114 | DOI | MR | Zbl

[16] Sintiari, Ni Luh Dewi; Trotignon, Nicolas (Theta, triangle)-free and (even hole, $K_{4}$ )-free graphs—part 1: Layered wheels, J. Graph Theory, Volume 97 (2021) no. 4, pp. 475-509 | DOI | MR | Zbl

Cited by Sources:

BROWSE ISSUES

About the journal

Editorial Board

Submit a paper

Journal Statistics