Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper resolves Melnikov's valency-variety problem by establishing tight lower bounds on the chromatic number of a graph $G$ in terms of its number of vertices $|V(G)|$ and the number of distinct vertex degrees $w(G)$. The derived bounds, $\chi(G)\ge\left\lceil1+\frac{2w(G)(w(G)-1)}{4w(G)(|V(G)|-w(G))+(|V(G)|-w(G)-1)^2}\right\rceil$ and $\chi(G)\ge\left\lceil\frac{\lfloor w(G)/2\rfloor}{|V(G)|-w(G)}\right\rceil$, are shown to be best possible. Explicit infinite families of graphs are constructed to demonstrate equality in these bounds, disproving Melnikov's conjectured strict inequality.
Melnikov's valency-variety problem is solved, revealing that the chromatic number is bounded by a specific function of graph size and degree diversity, with constructions proving these bounds are tight.
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*} Finally, we also construct an explicit infinite family of graphs attaining equality in both bounds. In particular, these examples show that Melnikov's proposed strict inequality is false and that the bounds above are best possible.