Melnikov's valency-variety problem

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph with $n=|V|\ge2$. Write $d(v)$ for the number of neighbors of $v$ and define its valency variety by \[ w(G)=|\{d(v):v\in V\}|. \] Thus degree values, not vertices or degree multiplicities, are counted. The chromatic number $\chi(G)$ is the least number of labels in a vertex coloring assigning distinct labels to adjacent vertices.

The proposed inequality is \[ \chi(G)>\left\lceil\frac{\lfloor w(G)/2\rfloor}{n-w(G)}\right\rceil \qquad\text{for every such }G. \] The floor and ceiling have their usual integer-rounding meanings. The denominator is positive: in a simple graph no isolated vertex and degree-$(n-1)$ vertex can coexist, so among the $n$ potential degrees $0,\ldots,n-1$ at least one is absent. Hence $1\le w(G)\le n-1$.

The strict inequality is essential. Since the chromatic number is integral, the assertion is equivalently a lower bound of one plus the displayed ceiling. It must hold regardless of the number of vertices realizing each degree, and no connectedness or minimum-degree condition is added. For a regular graph $w(G)=1$ the bound is only $\chi(G)>0$; the substantive regime involves many distinct degrees compared with the order. A counterexample must satisfy the exact strict comparison, rather than only a rounded or asymptotic approximation.

Short English statement

Does the diversity of vertex degrees force Melnikov’s stated strict lower bound on the chromatic number?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3242 (OPG-46575), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Melnikov's valency-variety problem. Original problem and discussion. http://www.openproblemgarden.org/op/melnikovs_valency_variety_problem.