Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1000-1009
DOI: 10.1137/25m1821879 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 08.07.2026. Verfasst von Maria Chudnovsky und 3 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, CRSNG, Government of Ontario.
Abstract (Originalsprache)
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.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- CRSNG
- Government of Ontario
- National Science Foundation
- Air Force Office of Scientific Research
- Fondation du Barreau du Québec
Zitieren
APA
Chudnovsky, M., Codsi, J., Hajebi, S., & Spirkl, S. (2026). Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests. SIAM Journal on Discrete Mathematics, 40(3), 1000-1009. https://doi.org/10.1137/25m1821879
Vancouver
Chudnovsky M, Codsi J, Hajebi S, Spirkl S. Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests. SIAM Journal on Discrete Mathematics. 2026;40(3):1000-1009. doi:10.1137/25m1821879
BibTeX
@article{Chudnovsky2026,
author = {Chudnovsky, Maria and Codsi, Julien and Hajebi, Sepehr and Spirkl, Sophie},
title = {Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1000--1009},
doi = {10.1137/25m1821879}
}
EUVIMED