{"id":"arxiv/2607.23918","url":"https://arxiv.org/abs/2607.23918","tags":["math.CO"],"score":0,"title":"A sharp Randić bound for König--Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng","domain":"math.CO","source":"arxiv","authors":["Pei Liu","Feiyu Nan","Suil O","Ruiling Zheng"],"reviews":0,"subject":"math.CO","summary":"Let $α'(G)$ be the matching number of a graph $G$, and let its Randić index be $R(G)=\\sum_{uv\\in E(G)}(d(u)d(v))^{-1/2}$. In 2006, Aouchiche, Hansen, and Zheng conjectured that the maximum of $R(G)-α'(G)$ over all $n$-vertex graphs is attained by the complete bipartite graph whose smaller part has $\\lfloor\\frac{n+4}{7}\\rfloor$ vertices; the conjecture has remained open since then. In this paper, we prove that every $n$-vertex König--Egerváry graph, and in particular every bipartite graph, satisfies \\[ R(G)\\le\\sqrt{α'(G)\\left(n-α'(G)\\right)}, \\] and we characterize the graphs attaining…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}