The PrP_r-K2,tK_{2,t}-free graph 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. The PrP_r-K2,tK_{2,t}-free graph conjecture. For any two positive integers rr and tt, the class of {Pr,K2,t}\{P_r,K_{2,t}\}-free graphs has bounded tree-independence number. This is presented as an interesting open case of the broader forbidden-path and biclique conjecture; boundedness is already known for classes of {Pr,K1,t}\{P_r,K_{1,t}\}-free graphs.

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).

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.