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

Abstract

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 $\Delta$, every graph with maximum degree at most $\Delta$ and sufficiently large treewidth contains either a subdivision of the $(k\times k)$-wall or the line graph of a subdivision of the $(k\times k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $t\ge 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally 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 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 $\Delta$, every graph with maximum degree at most $\Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(k\times 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\ge 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 $\Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $\Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.

Accepted manuscript; see DOI for journal version

References in corpus (3)

• Grid Induced Minor Theorem for Graphs of Small Degree
• Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
• On the tree-width of even-hole-free graphs

Cited by in corpus (7)

• Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
• Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
• Induced subgraphs and tree decompositions V. One neighbor in a hole
• Submodular functions and perfect graphs
• Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole
• Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
• Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs