Chi-boundedness conjecture for graphs of bounded induced matching treewidth
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.
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).
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
Sign in to submit a solution.
No solutions have been posted yet.