Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests

SIAM Journal on Discrete Mathematics 2026 Open access

Read full text
Authors: Maria Chudnovsky, Julien Codsi, Sepehr Hajebi, Sophie Spirkl
DOI: 10.1137/25m1821879
Cited by: 0

Abstract

Abstract. Let [Formula: see text] be a graph, and let [Formula: see text] be a hereditary class of theta-free graphs such that [Formula: see text]. We prove that if (a) [Formula: see text] is a forest, and (b) [Formula: see text] excludes the line graphs of all subdivisions of some wall, then the treewidth of every graph in [Formula: see text] is at most a polynomial function of its clique number. This is best possible in that both (a) and (b) are necessary for the existence of any function with the above property.

Fields of Study & Subjects

Advanced Graph Theory Research Advanced Combinatorial Mathematics Commutative Algebra and Its Applications

Publication details

Journal / source
SIAM Journal on Discrete Mathematics
Volume
40
Issue
3
Pages
1000–1009
Publication date
8 July 2026
Language
EN