Chi-boundedness conjecture for graphs of bounded induced matching treewidth

Let k,cNk,c\in\mathbb{N}. Consider graphs whose induced matching treewidth is at most kk, and write ω(G)\omega(G) and χ(G)\chi(G) for their clique and chromatic numbers, respectively.

Chi-boundedness conjecture. For any two integers k,cNk,c\in\mathbb{N} there exists an integer rr such that every graph with induced matching treewidth at most kk and clique number at most cc has chromatic number at most rr.

This proposes that bounded induced matching treewidth defines a χ\chi-bounded graph class, analogous to (tw,ω)(\operatorname{tw},\omega)-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

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.