Melnikov's valency-variety problem

Low ★ Graph Theory » Coloring » Vertex coloring

Author: Melnikov, L. S.— posted by asp on 2013-03-03

Status open low confidence

Melnikov's valency-variety problem asks whether $\chi(G) > \lceil \lfloor w(G)/2 \rfloor / (|V(G)| - w(G)) \rceil$ for every graph $G$ with at least two vertices, where $w(G)$ is the number of distinct degrees. The problem has been listed as open since its appearance in Jensen–Toft (1995), and no post-2013 paper establishing or refuting this bound was found in the literature search.

Reviewer notes. All 4+ search queries returned no verifiable post-2013 paper on this specific problem. The OPG page was unreachable (ECONNREFUSED), ScienceDirect returned 403, arXiv search returned HTTP 429. The problem appears too specialized to have attracted attention in the recent literature; it was already open in Jensen–Toft (1995, p. 90) and no evidence of subsequent progress was found. Status 'open' is assigned with low confidence because the absence of results may partly reflect search limitations rather than true inactivity.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 06) (web search enabled).

Problem. The valency-variety $ w(G) $ of a graph $ G $ is the number of different degrees in $ G $ . Is the chromatic number of any graph $ G $ with at least two vertices greater than $$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$

Discussion

According to Jensen and Toft [JT, p. 90], the problem is due to Melnikov and was mentioned by Vizing [V] and Zykov [Z]. According to Zykov [Z], Melnikov showed that the suggested lower bound would be best possible. A best possible upper bound on the chromatic number in terms of $ |V(G)| $ and $ w(G) $ is $ |V(G)| - \floor{ w(G) / 2 } $ as proved by Nettleton [N] and Dirac [D].

Bibliography

[D] G. A. Dirac. Valency-variey and chromatic number of abstract graphs. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 13, 59--64, 1964.
[JT] Tommy R. Jensen, Bjarne Toft: Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1995.
[N] R. E. Nettleton. Some generalized theorems on connectivity. Canad. J. Math. 12, 546--554, 1960.
★ [V] V. G. Vizing. Some unsolved problems in graph theory (in Russian). Uspekhi Mat. Nauk. 23, 117--134, 1968. English translation in Russian Math. Surveys 23, 125--141.
★ [Z] A. A. Zykov. Problem 11. In: H. Sachs, H.-J. Voss, and H. Walther, editors, Beiträge zur Graphentheorie vorgetragen auf dem Internationalen Kolloquium in Manebach DDR vom 9.-12. Mai 1967, page 228. B. G. Teubner, 1968.