TY - JOUR
T1 - Tree independence number I. (Even hole, diamond, pyramid)-free graphs
AU - Abrishami, Tara
AU - Alecu, Bogdan
AU - Chudnovsky, Maria
AU - Hajebi, Sepehr
AU - Spirkl, Sophie
AU - Vušković, Kristina
N1 - Publisher Copyright:
© 2024 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
PY - 2024/8
Y1 - 2024/8
N2 - The tree-independence number (Formula presented.), first defined and studied by Dallard, Milanič, and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass (Formula presented.) of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that (Formula presented.) has bounded (Formula presented.). Via existing results, this yields a polynomial-time algorithm for the Maximum Weight Independent Set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milanič, and Štorgel that in a hereditary graph class, (Formula presented.) is bounded if and only if the treewidth is bounded by a function of the clique number.
AB - The tree-independence number (Formula presented.), first defined and studied by Dallard, Milanič, and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass (Formula presented.) of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that (Formula presented.) has bounded (Formula presented.). Via existing results, this yields a polynomial-time algorithm for the Maximum Weight Independent Set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milanič, and Štorgel that in a hereditary graph class, (Formula presented.) is bounded if and only if the treewidth is bounded by a function of the clique number.
KW - algorithmic graph theory
KW - even-hole-free graphs
KW - structural graph theory
KW - tree independence number
KW - treewidth
UR - http://www.scopus.com/inward/record.url?scp=85191322628&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85191322628&partnerID=8YFLogxK
U2 - 10.1002/jgt.23104
DO - 10.1002/jgt.23104
M3 - Article
AN - SCOPUS:85191322628
SN - 0364-9024
VL - 106
SP - 923
EP - 943
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 4
ER -