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 -