{"id":"arxiv/2610.09649","url":"https://arxiv.org/abs/2610.09649","tags":["math.CO"],"score":0,"title":"Melnikov's Valency Variety Problem","domain":"math.CO","source":"arxiv","authors":["Zhanping Yang","Qinghou Zeng"],"reviews":0,"subject":"math.CO","summary":"Let $w(G)$ denote the number of distinct vertex degrees of a finite simple graph $G$. Melnikov asked for a lower bound on the chromatic number $χ(G)$ in terms of $|V(G)|$ and $w(G)$, and conjectured a strict bound of this type. We resolve Melnikov's valency-variety problem by proving that every graph $G$ with at least two vertices satisfies \\begin{equation*} χ(G)\\ge\\left\\lceil1+\\frac{2w(G)(w(G)-1)}{4w(G)(|V(G)|-w(G))+(|V(G)|-w(G)-1)^2}\\right\\rceil, \\end{equation*} and consequently \\begin{equation*} χ(G)\\ge\\left\\lceil\\frac{\\lfloor w(G)/2\\rfloor}{|V(G)|-w(G)}\\right\\rceil. \\end{equation*}…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}