Characterization of bounded γ/ρ graph classes

Question 9.1 · arXiv:2503.05562

arXiv Question high confidence— first stated 2025-03-07

Authors: Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky

Status partial high confidence

The full characterization of graph classes with bounded domination-packing ratio γ(G)/ρ(G) remains open. A follow-up paper (arXiv:2602.18402, Dúcz–Gujgiczer 2026) extends the list of classes with bounded ratio to chordal bipartite graphs and homogeneously orderable graphs (both with constant 2), and improves the planar bound from 10 to 7, but does not provide a characterization. The question of whether any structural characterization exists — especially in light of the 2-degenerate result ruling out purely sparse characterizations — is still unresolved.

Cited literature (1)

partial Domination and packing in graphs (2026)

Ákos Dúcz, Anna Gujgiczer · arXiv preprint · arXiv:2602.18402

Proves γ(G) ≤ 7ρ(G) for planar graphs (improving the prior bound of 10) and establishes γ(G) ≤ 2ρ(G) for chordal bipartite and homogeneously orderable graphs, extending the list of classes with bounded ratio but not providing the requested characterization.

Reviewer notes. arXiv:2602.18402 is co-authored by Gujgiczer, one of the original authors, and explicitly cites [BCG+25] (the source paper). It contributes new cases but leaves the characterization question open.

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

Question. Characterize those graph classes $\mathcal{G}$ for which there is a constant $c_{\mathcal{G}}$ such that $\dfrac{\gamma(G)}{\rho(G)}\leqslant c_{\mathcal{G}}$ for each $G\in\mathcal{G}$.

Context

In the conclusion, after extending both the list of graph classes with bounded $\gamma/\rho$ ratio and those with unbounded ratio (notably showing 2-degenerate graphs have bounded ratio), the authors note that Theorem 6.1 on 2-degenerate graphs rules out any characterization purely in terms of sparse graph classes.

Notes. Statement text is partially cut off in the provided content; the formula is inferred from context and from the identical formulation in Question 1.1.

Source paper

On graph classes with constant domination-packing ratio
Marthe Bonamy, Mónika Csikós, Anna Gujgiczer, Yelena Yuditsky · 2025-03-07
https://arxiv.org/abs/2503.05562