{"id":"arxiv/2605.03965","url":"https://arxiv.org/abs/2605.03965","tags":["math.CO","cs.DM"],"score":0,"title":"Tree-independence number of $P_5$-free graphs with no large bicliques","domain":"math.CO","source":"arxiv","authors":["Václav Blažej","J. Pascal Gollin","Tomáš Hons","Tomáš Masařík","Martin Milanič","Paweł Rzążewski","Ondřej Suchý","Alexandra Wesolek"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-05","reactions":{}}