Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 923-943 |
| Number of pages | 21 |
| Journal | Journal of Graph Theory |
| Volume | 106 |
| Issue number | 4 |
| DOIs | |
| State | Published - Aug 2024 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- algorithmic graph theory
- even-hole-free graphs
- structural graph theory
- tree independence number
- treewidth