TY - JOUR

T1 - Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Dibek, Cemil

AU - Hajebi, Sepehr

AU - Rzążewski, Paweł

AU - Spirkl, Sophie

AU - Vušković, Kristina

N1 - Publisher Copyright:
© 2023 Elsevier Inc.

PY - 2024/1

Y1 - 2024/1

N2 - This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all k and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of the (k×k)-wall or the line graph of a subdivision of the (k×k)-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For t≥2, a t-theta is a graph consisting of two nonadjacent vertices and three internally vertex-disjoint paths between them, each of length at least t. A t-pyramid is a graph consisting of a vertex v, a triangle B disjoint from v and three paths starting at v and vertex-disjoint otherwise, each joining v to a vertex of B, and each of length at least t. We prove that for all k,t and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a t-theta, or a t-pyramid, or the line graph of a subdivision of the (k×k)-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a t-theta for some t≥2). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every Δ and subcubic subdivided caterpillar T, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of T or the line graph of a subdivision of T as an induced subgraph.

AB - This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all k and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of the (k×k)-wall or the line graph of a subdivision of the (k×k)-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For t≥2, a t-theta is a graph consisting of two nonadjacent vertices and three internally vertex-disjoint paths between them, each of length at least t. A t-pyramid is a graph consisting of a vertex v, a triangle B disjoint from v and three paths starting at v and vertex-disjoint otherwise, each joining v to a vertex of B, and each of length at least t. We prove that for all k,t and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a t-theta, or a t-pyramid, or the line graph of a subdivision of the (k×k)-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a t-theta for some t≥2). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every Δ and subcubic subdivided caterpillar T, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of T or the line graph of a subdivision of T as an induced subgraph.

KW - Induced Subgraph

KW - Tree decomposition

KW - Treewidth

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

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

U2 - 10.1016/j.jctb.2023.10.005

DO - 10.1016/j.jctb.2023.10.005

M3 - Article

AN - SCOPUS:85175004566

SN - 0095-8956

VL - 164

SP - 371

EP - 403

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -