EUVIMEDEUVIMED entdecken
Crossref

Induced Subgraphs and Tree Decompositions XIX: Thetas and Forests

Maria Chudnovsky, Julien Codsi, Sepehr Hajebi, Sophie Spirkl

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →