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

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Paweł Rzążewski, Sophie Spirkl, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 Δ, 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.

Original languageEnglish (US)
Pages (from-to)371-403
Number of pages33
JournalJournal of Combinatorial Theory. Series B
Volume164
DOIs
StatePublished - Jan 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Induced Subgraph
  • Tree decomposition
  • Treewidth

Fingerprint

Dive into the research topics of 'Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree'. Together they form a unique fingerprint.

Cite this