REVIEW 7 cited by
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
read the original abstract
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs. Their result also implies a characterization of graph classes defined by finitely many forbidden induced subgraphs that are $(tw,\omega)$-bounded, that is, treewidth can only be large due to the presence of a large clique. This condition is known to be satisfied for any graph class with bounded tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milani\v{c}, and \v{S}torgel in 2024. Dallard et al. conjectured that $(tw,\omega)$-boundedness is actually equivalent to bounded tree-independence number. We address this conjecture in the context of graph classes defined by finitely many forbidden induced subgraphs and prove it for the case of graph classes excluding an induced star. We also prove it for subclasses of the class of line graphs, determine the exact values of the tree-independence numbers of line graphs of complete graphs and line graphs of complete bipartite graphs, and characterize the tree-independence number of $P_4$-free graphs, which implies a linear-time algorithm for its computation. Applying the algorithmic framework provided in a previous paper of the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes.
Forward citations
Cited by 7 Pith papers
-
Tree-alpha and excluding finitely many graphs
Hereditary classes defined by finitely many excluded induced subgraphs have bounded tree-α iff they are (tw,ω)-bounded, i.e., exclude K_{a,a}, forests with components of at most three leaves, and their line graphs.
-
Tree decompositions with small width, spread, order and degree
Every graph with treewidth k admits a tree-decomposition of width <=14k+13 with each vertex in <=deg(v)+1 bags, plus a second decomposition of width <=3k-1 with average three bags per vertex.
-
Excluding paths and bicliques
For {P_s,K_{t,t}}-free graphs, the maximum path length is at most 2^{ω(G)^c}, and treedepth is clique-polynomial.
-
Induced Erd\H{o}s--P\'osa property for long holes, long thetas, and beyond
For fixed t, both C_t and Θ_t have the induced Erdős–Pósa property for induced minors with hitting set size O(tk log k), implying O(tk log k)-dominated balanced separators and a QPTAS for MWIS in kΘ_t-induced-minor-fr...
-
Forcing monochromatic induced subgraphs
For any c and nonnull graphs H1..Ht there is n such that every c-edge-colored K_infty without a monochromatic induced join of the Hi's has its vertices covered by n sets in which, for each large set, some color class ...
-
Forcing monochromatic induced subgraphs
An edge-colored complete graph that avoids a monochromatic induced complete join can be partitioned into boundedly many simple pieces, in any number of overlapping colors.
-
Tree-independence number of $K_{1,d}$-free graph classes
Proves the Dallard et al. conjecture holds for outerstring graphs and sharpens bounds on tree-independence number for multiple K_{1,d}-free classes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.