The forbidden biclique and path conjecture for tree-independence number

For positive integers dd and ss, a graph is {Kd,d,Ps}\{K_{d,d},P_s\}-free if it has no induced subgraph isomorphic to Kd,dK_{d,d} or the ss-vertex path PsP_s. The biclique-and-path conjecture. For any two positive integers dd and ss, the class of {Kd,d,Ps}\{K_{d,d},P_s\}-free graphs has bounded tree-independence number. This is a special case of the finite-forbidden-subgraph conjecture. The case with P4P_4 is discussed as known, while the full statement for arbitrary dd and ss remains open.

Sources & referencesView supporting material

Primary source

Clément Dallard, Matjaž Krnc, O-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel and Sebastian Wiederrecht, “Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star”, arXiv:2402.11222 (2024).

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.