Induced packing treewidth II. Excluding a clique or a biclique
Abstract
The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. For a graph H, \emph{induced H-packing treewidth}, denoted by treepiH, is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of H intersecting that bag. This notion generalizes some previously studied parameters: when H=P1, it is equivalent to tree-independence number, and when H=P2, it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all a,t∈ ℕ, Ka,a-free graphs of bounded induced Pt-packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for t=2, and a result of Hajebi and Spirkl who showed that (Pt,Ka,a)-free graphs have bounded tree-independence number. \item If H is any fixed path or a star, then the class of graphs of bounded induced H-packing treewidth is χ-bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for H=P2. \item Finally, we study the relationship between induced packing treewidth and \emph{sim-width}, a width parameter based on branch decompositions. We show that, although \emph{sim-width} and induced P3-packing treewidth are incomparable, graphs of bounded sim-width that exclude all \emph{H-obstructions}---certain graphs that force large induced H-packing treewidth---have bounded induced H-packing treewidth. This simultaneously generalizes and resolves questions posed by Abrishami et al. [SIAM J. Discrete Math., 2025] and Brettell et al. [European J. Comb., 2025]. \end{itemize}
Related
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
- An improved bound on the treewidth of planar graphs excluding a grid minor
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
- Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
- Asymptotic dimension of graphs excluding an induced or fat minor
BibTeX
@misc{nikabadi2026induced,
title = {{Induced packing treewidth II. Excluding a clique or a biclique}},
author = {Amir Nikabadi and Paweł Rzążewski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21615},
eprint = {2609.21615},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21615},
}
RIS
TY - UNPB
TI - Induced packing treewidth II. Excluding a clique or a biclique
AU - Amir Nikabadi
AU - Paweł Rzążewski
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21615
UR - https://arxiv.org/abs/2609.21615
AB - The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. For a graph H, \emph{induced H-packing treewidth}, denoted by treepi_H, is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of H intersecting that bag. This notion generalizes some previously studied parameters: when H=P_1, it is equivalent to tree-independence number, and when H=P_2, it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all a,t∈ ℕ, K_a,a-free graphs of bounded induced P_t-packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for t=2, and a result of Hajebi and Spirkl who showed that (P_t,K_a,a)-free graphs have bounded tree-independence number. \item If H is any fixed path or a star, then the class of graphs of bounded induced H-packing treewidth is χ-bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for H=P_2. \item Finally, we study the relationship between induced packing treewidth and \emph{sim-width}, a width parameter based on branch decompositions. We show that, although \emph{sim-width} and induced P_3-packing treewidth are incomparable, graphs of bounded sim-width that exclude all \emph{H-obstructions}---certain graphs that force large induced H-packing treewidth---have bounded induced H-packing treewidth. This simultaneously generalizes and resolves questions posed by Abrishami et al. [SIAM J. Discrete Math., 2025] and Brettell et al. [European J. Comb., 2025]. \end{itemize}
ER -