Dallard et al.'s forbidden-path and biclique conjecture for tree-independence number

For a family F\mathcal{F} of graphs, a graph GG is F\mathcal{F}-free if no induced subgraph of GG is isomorphic to a graph in F\mathcal{F}. Let PrP_r be the path with rr vertices and let Ks,tK_{s,t} be the complete bipartite graph with parts of sizes ss and tt, respectively. Dallard et al.'s conjecture. For any two positive integers rr and tt, the class of {Pr,Kt,t}\{P_r,K_{t,t}\}-free graphs has bounded tree-independence number. A weakening giving a polylogarithmic bound is known, and the conjecture has been confirmed for r4r\leq 4, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.