A Negative Answer to Melnikov's Valency-Variety Problem

The valency-variety \(w(G)\) of a graph \(G\) is the number of distinct vertex degrees of \(G\). In a problem recorded by Vizing in 1968 and later listed by Jensen and Toft, Melnikov conjectured that every graph \(G\) with \(n\ge 2\) vertices satisfies \(\chi(G)>\lceil\lfloor w(G)/2\rfloor/(n-w(G))\rceil\). We show that the conjecture is false. The inequality is equivalent to \((2\chi(G)-1)(n-w(G))\ge n-1\). For every \(k\ge 3\) we construct explicit connected \(k\)-chromatic graphs that attain equality in this form, a \(k\)-chromatic counterexample on \(14k-5\) vertices (it has one isolated vertex), and a connected \(k\)-chromatic counterexample on \(22k-9\) vertices. A blow-up construction gives connected \(k\)-chromatic graphs with \(n-w=16n/(32k-13)<n/(2k-1)\), so the inequality fails by an amount that grows linearly in \(n\). On the positive side, the inequality holds for all bipartite graphs, and a counting argument based on Turán's theorem shows \(n-w\ge\mu_k n-O(1)\) for every \(K_{k+1}\)-free graph, where \(\mu_3=(3-\sqrt5)/4\approx 0.191\) (Melnikov's bound asks for \(1/5\), and our constructions give \(16/83\approx 0.193\)). The same argument, evaluated exactly by computer and combined with the bipartite case, shows that every graph with at most \(36\) vertices satisfies Melnikov's inequality. So the smallest counterexample has \(37\) vertices. For \(3\le k\le 60\), the smallest \(k\)-chromatic counterexample has \(14k-5\) vertices, and the smallest one without isolated vertices (in particular, the smallest connected one) has \(22k-9\) vertices. This is an unrefereed note.