DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.77

Tree-Independence Number of P₅-Free Graphs with No Large Bicliques

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

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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_{𝓁,𝓁} 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.

Cite as

Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra Wesolek. Tree-Independence Number of P₅-Free Graphs with No Large Bicliques. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ESA.2026.77,
  author =	{Bla\v{z}ej, V\'{a}clav and Gollin, J. Pascal and Hons, Tom\'{a}\v{s} and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Milani\v{c}, Martin and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej and Wesolek, Alexandra},
  title =	{{Tree-Independence Number of P₅-Free Graphs with No Large Bicliques}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.77},
  URN =		{urn:nbn:de:0030-drops-272138},
  doi =		{10.4230/LIPIcs.ESA.2026.77},
  annote =	{Keywords: tree-independence number, independence degeneracy, independence treewidth, P₅-free graphs}
}

@InProceedings{blazej_et_al:LIPIcs.ESA.2026.77,
  author =	{Bla\v{z}ej, V\'{a}clav and Gollin, J. Pascal and Hons, Tom\'{a}\v{s} and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Milani\v{c}, Martin and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej and Wesolek, Alexandra},
  title =	{{Tree-Independence Number of P₅-Free Graphs with No Large Bicliques}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.77},
  URN =		{urn:nbn:de:0030-drops-272138},
  doi =		{10.4230/LIPIcs.ESA.2026.77},
  annote =	{Keywords: tree-independence number, independence degeneracy, independence treewidth, P₅-free graphs}
}

Search Results

Documents authored by Gollin, J. Pascal

Tree-Independence Number of P₅-Free Graphs with No Large Bicliques

Abstract

Cite as

Thanks for your feedback!

Could not send message