Tree-independence conjecture for biclique-free graphs of bounded induced matching treewidth

For a graph GG, its induced matching treewidth is the minimum, over tree decompositions, of the maximum size of an induced matching whose edges intersect one bag; its tree-independence number is the minimum, over tree decompositions, of the maximum independence number of a bag. Let Kt,tK_{t,t} denote the complete bipartite graph with tt vertices in each part.

Tree-independence conjecture. For any two integers k,tNk,t\in\mathbb{N} there exists an integer rr such that every graph with induced matching treewidth at most kk and no induced subgraph isomorphic to Kt,tK_{t,t} has tree-independence number at most rr.

This would generalize known results relating induced matching treewidth, treewidth, and tree-independence number for classes excluding a fixed biclique. The conjecture remains open.

Sources & referencesView supporting material

Primary source

Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski and Kenny Štorgel, “Tree decompositions meet induced matchings: beyond Max Weight Independent Set”, arXiv:2402.15834 (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.