Tree-independence number of $P_5$-free graphs with no large bicliques

Václav Blažej; J. Pascal Gollin; Tomáš Hons; Tomáš Masařík; Martin Milanič; Paweł Rzążewski; Ondřej Suchý; Alexandra Wesolek

Tree-independence number of $P_5$-free graphs with no large bicliques

Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, Alexandra Wesolek

arXivarxiv/2605.03965May 5, 2026math.COscore 0

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_{\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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.03965
curl -X POST /api/v1/records/arxiv/2605.03965/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.03965/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'