Chi-boundedness conjecture for graphs of bounded induced matching treewidth
Let . Consider graphs whose induced matching treewidth is at most , and write and for their clique and chromatic numbers, respectively.
Chi-boundedness conjecture. For any two integers there exists an integer such that every graph with induced matching treewidth at most and clique number at most has chromatic number at most .
This proposes that bounded induced matching treewidth defines a -bounded graph class, analogous to -boundedness. The assertion is stated as an open direction in the paper.
References
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).
Additional references
3 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:2204.14230, arXiv:1304.1718.
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
No solutions have been posted yet.