Domination numbers satisfy γ(G□H) ≥ γ(G)γ(H) for the Cartesian product of any two graphs.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
For all graphs $G$ and $H$, $\gamma(G \square H) \ge \gamma(G)\,\gamma(H)$, where $\gamma$ denotes the domination number and $\square$ the Cartesian product.
Assessment
Renown 5/5
The central open problem of domination theory for six decades; active work as recently as July 2026 (constant-factor improvements by Steiner and by Aliabadi-Krop).
Attackability 2/5
Finite witness (a pair of graphs) with an ILP oracle, but decades of minimal-counterexample theorems (no chordal or claw-free factors, factor domination numbers at least 4) fence the search into a hard region.
- finite witness
- 5/5
- oracle cost
- 3/5
- freshness
- 1/5
- seedability
- 3/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.