Aouchiche–Hansen–Zheng conjecture on the Randić index and matching number
Let be a connected graph on vertices, where . Write for its Randić index and let denote its matching number. Define
Aouchiche–Hansen–Zheng conjecture. One has
with equality if and only if .
The conjecture proposes the extremal connected graph for the difference between the Randić index and matching number. It was disproved by the existence of a counterexample; the corresponding restricted extremal problem for subcubic graphs was solved by Du, Hu, and collaborators.
References
Primary source
Pei Liu, Feiyu Nan, Suil O and Ruiling Zheng, “A sharp Randić bound for König–Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng”, arXiv:2607.23918 (2026).
Additional references
4 papers in this index state this conjecture (2009–2026). The statement above is taken from the most recent of them; the others are arXiv:1607.08258, arXiv:1104.0426, arXiv:0906.5230.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.