Tree-independence number of P5-free graphs with no large bicliques
Abstract
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties; however, the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique Kℓ,ℓ forces tree-independence number at least ℓ. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and ℓ, {Pt,Kℓ,ℓ}-free graphs have bounded tree-independence number. We prove this conjecture for t=5 by showing that every {P5,Kℓ,ℓ}-free graph has tree-independence number at most 4ℓ−4. We also obtain related bounds for the weaker parameter of α-degeneracy and answer a question of Hilaire, Milanič, and Vasić whether tree-independence number of {P5,Kℓ,ℓ}-free graphs exceeds ℓ by at most an additive constant.
Related
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
- Tree Independence Number III. Thetas, Prisms and Stars
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
- Strong complete immersions in graphs with independence number two
BibTeX
@misc{blazej2026treeindependence,
title = {{Tree-independence number of $P_5$-free graphs with no large bicliques}},
author = {Václav Blažej and J. Pascal Gollin and Tomáš Hons and Tomáš Masařík and Martin Milanič and Paweł Rzążewski and Ondřej Suchý and Alexandra Wesolek},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.03965},
eprint = {2605.03965},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.03965},
}
RIS
TY - UNPB
TI - Tree-independence number of P_5-free graphs with no large bicliques
AU - Václav Blažej
AU - J. Pascal Gollin
AU - Tomáš Hons
AU - Tomáš Masařík
AU - Martin Milanič
AU - Paweł Rzążewski
AU - Ondřej Suchý
AU - Alexandra Wesolek
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2605.03965
UR - https://arxiv.org/abs/2605.03965
AB - The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties; however, the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_ℓ,ℓ forces tree-independence number at least ℓ. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and ℓ, {P_t,K_ℓ,ℓ}-free graphs have bounded tree-independence number. We prove this conjecture for t=5 by showing that every {P_5,K_ℓ,ℓ}-free graph has tree-independence number at most 4ℓ−4. We also obtain related bounds for the weaker parameter of α-degeneracy and answer a question of Hilaire, Milanič, and Vasić whether tree-independence number of {P_5,K_ℓ,ℓ}-free graphs exceeds ℓ by at most an additive constant.
ER -