Graph-theory open problems

Constant domination-packing ratio per graph class

AX_domination_packing_ratio_bounded_given_class

Source: arXiv:2503.05562 — On graph classes with constant domination-packing ratio

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

Diagnostic tag ill-posed high confidence

With no graph class specified the question has no single answer, and its universal interpretation is false even for the hereditary class of split graphs.

Caveat. The counterexamples settle only the universal reading; they do not characterize all classes with bounded ratio and may overlap known negative examples.

Attack verdicts are unrefereed model self-reports. An ill-posed label is a diagnostic of the catalog statement supplied to the model, not a literature-review status or a peer-reviewed result.

Assessed 2026-09-01 with gpt-5.6-sol · view the full attack artifact.

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

Related conjectures

  • same conjecture as Characterization of bounded γ/ρ graph classes partial Both nodes come from the same paper (arXiv:2503.05562) and concern the same quantity, the ratio gamma(G)/rho(G), and the same condition, existence of a class-dependent constant c_G bounding it. The source is the paper's guiding question stated as a schema over graph classes ('Given a graph class G, is there a constant c_G ...?'); answering it for every class is precisely the target's conclusion-section request to 'characterize those graph classes' admitting such a constant. Neither is a proposition with a truth value; both denote the one open research problem the paper is organized around, restated in sharpened form at the end. Caveat: the phrasings differ in form (per-class decision question vs. characterization), which is why confidence is medium rather than high.
  • implied by Characterization of bounded γ/ρ graph classes partial Instance-of-general relation, both questions from the same paper: the target asks, for a given class G, whether a constant c_G bounds gamma/rho over G; the source asks to characterize exactly the classes for which such a constant exists. Any resolution of the characterization answers the per-class question for each given class, so the source is the stronger problem and solving it solves the target. Direction as claimed is correct. Arguably near-equivalent phrasings (answering every instance constitutes an extensional characterization), but the claimed implication certainly holds.

View in the relation graph — relations are AI-reviewed, not formally verified.