The bounded tree-independence conjecture for {Pk,Kt,t}\{P_k,K_{t,t}\}-free graphs

About 1 year old · traced to

For positive integers kk and tt, let a graph be {Pk,Kt,t}\{P_k,K_{t,t}\}-free if it contains no induced subgraph isomorphic to the kk-vertex path PkP_k or to Kt,tK_{t,t}.

Bounded tree-independence conjecture. For any two positive integers kk and tt, the class of {Pk,Kt,t}\{P_k,K_{t,t}\}-free graphs has bounded tree-independence number.

The conjecture is open already in this special case, as stated in the source.

References

Primary source

Claire Hilaire, Martin Milanič and Đorđe Vasić, “Treewidth versus clique number. V. Further connections with tree-independence number”, arXiv:2505.12866 (2025).

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.