MathDB

Melnikov’s valency variety problem

Let GG be a finite simple graph with n=∣V(G)∣≥2n=|V(G)|\ge 2, chromatic number χ(G)\chi(G), and valency variety w(G)w(G), where w(G)w(G) is the number of distinct vertex degrees occurring in GG. Determine the sharp lower bound for χ(G)\chi(G) in terms of nn and w(G)w(G); in particular, determine whether Melnikov's proposed strict lower bound holds for every such graph.

References

Primary source

arXiv

Additional references

chromatic-graph-theorygraph-theory
Posted · edited

Progress summary

Refreshed
Claimed solved

A new unrefereed preprint claims the conjectured bound is false and replaces it with sharp bounds, but the result has not been independently checked.

Melnikov’s problem asks for the sharp relationship between a graph’s chromatic number and its valency variety. It is due to L. S. Melnikov and was mentioned by Vizing and Zykov.

Known results

Dirac’s 1964 work, with the result also attributed to Nettleton, gives a best-possible upper bound involving the valency variety and the other parameter in the original formulation.

October 2026 sharp-bound claim

Zhanping Yang and Qinghou Zeng report that the proposed strict inequality is false, prove two replacement bounds, and construct equality examples for both. This would settle the stated extremal problem, but the preprint is unrefereed and lacks independent corroboration.

planetmath.org · en.wikipedia.org · openai.com · pmc.ncbi.nlm.nih.gov · openai.com · ebsco.com · cdn.openai.com · export.arxiv.org · export.arxiv.org · arxiv.org · arxiv.org · ar5iv.labs.arxiv.org · mathstodon.xyz · mathstodon.xyz · mathstodon.xyz · mathstodon.xyz · mathstodon.xyz · quantamagazine.org · x.com

Current status (as of October 2026): The original strict conjecture is claimed refuted and replaced by sharp bounds, but that claim remains unverified.

Sources

Solutions 0

No solutions have been posted yet.