arXiv | tags:[ graph theory parameterized complexity ]
Tree-Independence Number of P5-Free Graphs with No Large Bicliques
with Jochen Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra WesolekThe tree-independence number of a graph is the minimum, over all tree-decompositions, of the largest independent set contained in a single bag. Classes of graphs with bounded tree-independence number enjoy strong structural and algorithmic properties, but the parameter can blow up even in fairly restricted classes – for instance, an induced biclique $K_{\ell,\ell}$ alone forces tree-independence number at least $\ell$. This raises the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes.
Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht conjectured that for all $t$ and $\ell$, every ${P_t, K_{\ell,\ell}}$-free graph has bounded tree-independence number. We prove this conjecture for $t = 5$: every ${P_5, K_{\ell,\ell}}$-free graph has tree-independence number at most $4\ell$. We also derive related bounds for the weaker parameter of $\alpha$-degeneracy.