2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27213 2026-08-25T13:18:18Z ddc:004 open_access

Tree-Independence Number of P₅-Free Graphs with No Large Bicliques Blažej, Václav Gollin, J. Pascal Hons, Tomáš Masařík, Tomáš Milanič, Martin Rzążewski, Paweł Suchý, Ondřej Wesolek, Alexandra tree-independence number independence degeneracy independence treewidth P₅-free graphs 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_{𝓁,𝓁} 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₅,K_{𝓁,𝓁}}-free graph has tree-independence number at most 4𝓁. We also obtain related bounds for the weaker parameter of α-degeneracy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 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 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.77 urn:nbn:de:0030-drops-272138 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.77 eng https://creativecommons.org/licenses/by/4.0/legalcode