Tree-independence number of $P_5$-free graphs with no large bicliques
2026-05-05 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a graph property called tree-independence number, which measures how large an independent set can be inside certain parts of a tree-like decomposition of the graph. They focus on graphs that do not contain long paths (specifically of length 5) or large complete bipartite subgraphs (bicliques) as induced subgraphs. The authors prove a conjecture that such graphs have bounded tree-independence number, showing it is at most 4 times the size of these bicliques. They also provide related results for a similar concept called α-degeneracy.
tree-independence numbertree-decompositionindependent setinduced subgraphbicliqueP_t-free graphsK_{ℓ,ℓ}-free graphshereditary graph classesα-degeneracygraph theory
Authors
Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, Alexandra Wesolek
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, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique $K_{\ell,\ell}$ forces tree-independence number at least $\ell$. 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 $\ell$, every $\{P_t,K_{\ell,\ell}\}$-free graph has bounded tree-independence number. We prove this conjecture for $t=5$ by showing that every $\{P_5,K_{\ell,\ell}\}$-free graph has tree-independence number at most $4\ell$. We also obtain related bounds for the weaker parameter of $α$-degeneracy.