Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
Abstract
The tree-independence number tree−α(G), the induced matching treewidth tree−μ(G), and the sim-width simw(G) are graph parameters defined in terms of tree or branch decompositions. We establish two polynomial bounds for the tree-independence number of induced Kt,t-free graphs, one in terms of sim-width and the other in terms of induced matching treewidth. Abrishami et al. (SIDMA, 2025) and Brettell et al. (EJC, 2025) asked whether bounded sim-width, together with the exclusion of an induced Kt,t, implies bounded tree-independence number. We answer this question by proving that, for integers t≥ 2 and s≥ 1, every induced Kt,t-free graph G with simw(G)≤ s satisfies tree−α(G)=Ot((s+1)2t2−2t). This also proves a polynomial strengthening of a conjecture of Bešter Štorgel et al. (arXiv, 2026) concerning induced K1,t-free graphs and improves a theorem of Alon et al. (arXiv, 2025) by reducing the exponent from 3t2+1 to 2t2−2t. Alon et al. (arXiv, 2025) asked whether, for fixed induced matching treewidth, the tree-independence number is polynomially bounded in t. Using a VC-dimension argument, we answer this question affirmatively by showing that, for integers μ≥ 1 and t≥ 2, every induced Kt,t-free graph G with tree−μ(G)≤μ satisfies tree−α(G)=tOμ(1).
Related
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- Strong complete immersions in graphs with independence number two
- Connected graphs with equal independence number and radius
- Independence number, essential connectivity and the distance spectral radius of graphs
BibTeX
@misc{niu2026simwidth,
title = {{Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced $K_t,t$-Free Graphs}},
author = {Mengyuan Niu and Xiumei Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18648},
eprint = {2609.18648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18648},
}
RIS
TY - UNPB
TI - Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced K_t,t-Free Graphs
AU - Mengyuan Niu
AU - Xiumei Wang
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18648
UR - https://arxiv.org/abs/2609.18648
AB - The tree-independence number tree−α(G), the induced matching treewidth tree−μ(G), and the sim-width simw(G) are graph parameters defined in terms of tree or branch decompositions. We establish two polynomial bounds for the tree-independence number of induced K_t,t-free graphs, one in terms of sim-width and the other in terms of induced matching treewidth. Abrishami et al. (SIDMA, 2025) and Brettell et al. (EJC, 2025) asked whether bounded sim-width, together with the exclusion of an induced K_t,t, implies bounded tree-independence number. We answer this question by proving that, for integers t≥ 2 and s≥ 1, every induced K_t,t-free graph G with simw(G)≤ s satisfies tree−α(G)=O_t((s+1)^2t^2−2t). This also proves a polynomial strengthening of a conjecture of Bešter Štorgel et al. (arXiv, 2026) concerning induced K_1,t-free graphs and improves a theorem of Alon et al. (arXiv, 2025) by reducing the exponent from 3t^2+1 to 2t^2−2t. Alon et al. (arXiv, 2025) asked whether, for fixed induced matching treewidth, the tree-independence number is polynomially bounded in t. Using a VC-dimension argument, we answer this question affirmatively by showing that, for integers μ≥ 1 and t≥ 2, every induced K_t,t-free graph G with tree−μ(G)≤μ satisfies tree−α(G)=t^O_μ(1).
ER -