Induced subgraphs and tree decompositions VII. Basic obstructions in H-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

Abstract

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w(t) such that every graph in C with treewidth more than w(t) contains an induced subgraph isomorphic to one of the following: the complete graph Kt, the complete bipartite graph Kt,t, a subdivision of the (t×t)-wall or the line graph of a subdivision of the (t×t)-wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η, a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series.

Original languageEnglish (US)
Pages (from-to)443-472
Number of pages30
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 VII. Basic obstructions in H-free graphs'. Together they form a unique fingerprint.

Cite this