Dallard et al.'s forbidden-path and biclique conjecture for tree-independence number
Dallard et al.'s forbidden-path and biclique conjecture for tree-independence number
For a family of graphs, a graph is -free if no induced subgraph of is isomorphic to a graph in . Let be the path with vertices and let be the complete bipartite graph with parts of sizes and , respectively. Dallard et al.'s conjecture. For any two positive integers and , the class of -free graphs has bounded tree-independence number. A weakening giving a polylogarithmic bound is known, and the conjecture has been confirmed for , but it remains open in general.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, Julien Codsi, J. Pascal Gollin, Martin Milanič and Varun Sivashankar, “Tree-independence number and forbidden induced subgraphs: excluding a 6-vertex path and a (2,t)-biclique”, arXiv:2604.01999 (2026).
Additional references
5 papers in this index state this conjecture (2024–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.23887, arXiv:2511.05285, arXiv:2505.12866, arXiv:2402.11222.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.