Tree-independence conjecture for biclique-free graphs of bounded induced matching treewidth
Tree-independence conjecture for biclique-free graphs of bounded induced matching treewidth
For a graph , 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 denote the complete bipartite graph with vertices in each part.
Tree-independence conjecture. For any two integers there exists an integer such that every graph with induced matching treewidth at most and no induced subgraph isomorphic to has tree-independence number at most .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.