γ(G) ≤ h(α₂(G)) graph class characterization
Problem 2 · arXiv:2601.15082
Status open high confidence
Problem 2 is explicitly stated as open in the source paper itself: the authors note that their main result (Theorem 9, characterizing sparse monotone classes with bounded domination-to-2-independence ratio) does not resolve the relaxed question, because classes such as C_{k,d} can have domination tied to 2-independence yet an unbounded ratio. The paper concludes that Problem 2 for sparse monotone graph classes remains a natural open question. No follow-up paper addressing this problem was found in a web search conducted in May 2026.
Reviewer notes. The paper was published 2026-01-21 (only ~4 months before this review). The HTML version of the paper confirms Problem 2 is open: 'Problem 2 for sparse monotone graph classes remains as a natural open question.' No internal references were supplied for this problem. No follow-up was found in the indexed literature.
Context
A graph class $\mathcal{G}$ has domination tied to 2-independence if there exists a function $h$ such that $\gamma(G)\leq h(\alpha_{2}(G))$ holds for every graph $G\in\mathcal{G}$. This is a relaxation of Problem 1, which requires $h$ to be linear; the authors remark that even this relaxed version seems non-trivial.
Source paper
Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio
Marthe Bonamy, Zdeněk Dvořák, Lukas Michel, David Mikšaník · 2026-01-21
https://arxiv.org/abs/2601.15082