Bounded domination-to-2-independence ratio characterization
Problem 1 · arXiv:2601.15082
Status open high confidence
Problem 1 asks which graph classes have bounded domination-to-2-independence ratio (i.e., sup gamma(G)/alpha_2(G) < infinity). The source paper itself (Theorem 4) gives an exact characterization for monotone graph classes with bounded average degree: such a class has bounded ratio if and only if it contains no cascades of arbitrarily large slope. However, the question remains fully open for hereditary graph classes (closed under induced subgraphs) and for dense graphs. No follow-up paper resolving the general problem was found in the four months since posting.
Reviewer notes. The source paper itself provides the main progress on Problem 1, characterizing the bounded-ratio property within sparse monotone graph classes. The general question — covering hereditary classes and dense graphs — is explicitly left open (Problem 2 in the paper concerns a related non-linear variant). No citing or follow-up paper was found via web search as of 2026-05-14.
Context
The domination-to-2-independence ratio of a graph class $\mathcal{G}$ is defined as $\sup_{G\in\mathcal{G}}\tfrac{\gamma(G)}{\alpha_{2}(G)}$. Since the fractional relaxations of domination number and $2$-independence number coincide, a bounded ratio would allow both parameters to be approximated via their common fractional relaxation, computable in polynomial time. The problem has been studied for trees, strongly chordal graphs, dually chordal graphs, outerplanar graphs, and other sparse graph classes.
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