PreprintCC BY 4.0arXiv
A 2/3 Bound for Vizing's Conjecture
Abstract
Vizing's conjecture, dating back to 1963, asserts that γ(Gmathbin□H) ≥ γ(G)γ(H) for all finite graphs G and H, where γ denotes the domination number and □ denotes the Cartesian product. In 2000, Clark and Suen proved the universal bound γ(Gmathbin□H) ≥ 1/2γ(G)γ(H). Recently, Steiner obtained the first constant-factor improvement of the Clark--Suen bound, proving that γ(Gmathbin□H) ≥ (5+√(73))/24γ(G)γ(H) ≈ 0.5643 γ(G)γ(H). In this paper, we further improve the universal constant by proving that γ(Gmathbin□H) ≥ 2/3γ(G)γ(H) for all finite graphs G and H. Thus, we raise the best known universal constant in the approximate form of Vizing's conjecture from (5+√(73))/24 to 2/3.
Related
BibTeX
@misc{aliabadi2026bound,
title = {{A $2/3$ Bound for Vizing's Conjecture}},
author = {Mohsen Aliabadi and Elliot Krop},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.01109},
eprint = {2607.01109},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.01109},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A 2/3 Bound for Vizing's Conjecture
AU - Mohsen Aliabadi
AU - Elliot Krop
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2607.01109
UR - https://arxiv.org/abs/2607.01109
AB - Vizing's conjecture, dating back to 1963, asserts that γ(Gmathbin□H) ≥ γ(G)γ(H) for all finite graphs G and H, where γ denotes the domination number and □ denotes the Cartesian product. In 2000, Clark and Suen proved the universal bound γ(Gmathbin□H) ≥ 1/2γ(G)γ(H). Recently, Steiner obtained the first constant-factor improvement of the Clark--Suen bound, proving that γ(Gmathbin□H) ≥ (5+√(73))/24γ(G)γ(H) ≈ 0.5643 γ(G)γ(H). In this paper, we further improve the universal constant by proving that γ(Gmathbin□H) ≥ 2/3γ(G)γ(H) for all finite graphs G and H. Thus, we raise the best known universal constant in the approximate form of Vizing's conjecture from (5+√(73))/24 to 2/3.
ER -