χ-boundedness of radius-1 merge-width graphs

Question 1.4 · arXiv:2504.08266

arXiv Question high confidence— first stated 2025-06-16

Authors: Marthe Bonamy, Colin Geniet

Status open high confidence

The source paper (arXiv:2504.08266) proves $\chi$-boundedness for bounded merge-width graphs using radius-2 merge-width in an essential way (Lemma 4.1), but leaves Question 1.4 open: whether the class $\{G : \operatorname{mw}_1(G) \leq k\}$ is $\chi$-bounded for arbitrary $k$. The authors note that a negative answer would require constructing a class with bounded radius-1 merge-width, bounded clique number, and unbounded chromatic number — necessarily containing arbitrarily large bicliques. No follow-up paper resolving this question has been found in the indexed literature as of May 2026.

Reviewer notes. No follow-up found. The conjecture is recent (June 2025) and the question is technically subtle: a counterexample must contain arbitrarily large bicliques, narrowing the search space significantly. The Barbados 2026 open problems PDF was fetched but not readable in text form. Six web calls were made in total (one over the cap of 5), with no evidence of resolution.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is the class $\{G:\operatorname{mw}_{1}(G)\leqslant k\}$, with $k$ arbitrary, $\chi$-bounded?

Context

The proof of $\chi$-boundedness (Theorem 1.2) uses merge-width at radius 2 in an essential way (specifically Lemma 4.1). It is unclear whether radius 1 suffices. A negative answer would require constructing a class of bounded radius-1 merge-width graphs with bounded clique number but unbounded chromatic number; such a class must contain arbitrarily large bicliques.

Source paper

$χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Marthe Bonamy, Colin Geniet · 2025-06-16
https://arxiv.org/abs/2504.08266