
AbstractThe tree‐independence number , 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 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 has bounded . 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, is bounded if and only if the treewidth is bounded by a function of the clique number.
even-hole-free graphs, tree independence number, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), structural graph theory, treewidth, FOS: Mathematics, 511, Mathematics - Combinatorics, Combinatorics (math.CO), algorithmic graph theory, Trees
even-hole-free graphs, tree independence number, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), structural graph theory, treewidth, FOS: Mathematics, 511, Mathematics - Combinatorics, Combinatorics (math.CO), algorithmic graph theory, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
