Constant domination-packing ratio per graph class

Question 1.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

Question 1.1 asks for which graph classes the domination-packing ratio $\gamma(G)/\rho(G)$ is bounded by a class-specific constant. The source paper itself gives positive answers for 2-degenerate, AT-free, and unit-disk graphs, with improved bounds for planar graphs and graphs of bounded treewidth or twin-width. A 2026 follow-up (arXiv:2602.18402) extends the positive answers further to chordal bipartite graphs and homogeneously orderable graphs, and provides an improved bound for planar graphs and a direct proof for trees. The general question — whether every natural graph class admits such a constant — remains open.

Cited literature (1)

partial Domination and packing in graphs (2026)

unknown (not extracted from fetch) · arXiv preprint · arXiv:2602.18402

Extends positive answers to the domination-packing ratio question to chordal bipartite graphs and homogeneously orderable graphs, gives an improved bound for planar graphs, and provides a simplified direct proof for trees.

Reviewer notes. The source paper already gives a rich set of positive answers to Question 1.1 for specific graph classes. The follow-up arXiv:2602.18402 (verified via WebFetch) directly continues this research thread. Authors of 2602.18402 were not extracted from the abstract page. The general meta-question of characterising all graph classes with bounded ratio remains open.

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

Question. Given a graph class $\mathcal{G}$, is there a constant $c_{\mathcal{G}}$ such that $$\frac{\gamma(G)}{\rho(G)}\leqslant c_{\mathcal{G}}\quad\text{ for each }\quad G\in\mathcal{G}~{}~{}?$$

Context

The paper studies the ratio between the dominating number $\gamma(G)$ and the packing number $\rho(G)$ of a graph $G$. A positive answer immediately gives the bound $c_{\mathcal{G}}$ on the integrality gap of both the dominating and the packing integer programs for any $G\in\mathcal{G}$.

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