Metraipolis › archive › dc_403fdddac83d
Melnikov's Valency Variety Problem — arXiv:2610.09649
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09649
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:44:02.192Z
- SHA-256 of the archived text
28ffdbde75cadf06c89f88dd0dd1ba7dd12b57a49564f7d4bed5a6a013e9c958- Stable URL of this page
https://metraipolis.com/documento/dc_403fdddac83d
How to cite
Melnikov's Valency Variety Problem — arXiv:2610.09649 — arXiv (en), https://arxiv.org/abs/2610.09649 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_403fdddac83d (Metraipolis archive dc_403fdddac83d, sha256 28ffdbde75cadf06c89f88dd0dd1ba7dd12b57a49564f7d4bed5a6a013e9c958)
BibTeX
@misc{dc403fdddac83d,
title = {Melnikov's Valency Variety Problem — arXiv:2610.09649},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09649},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_403fdddac83d; sha256 28ffdbde75cadf06c89f88dd0dd1ba7dd12b57a49564f7d4bed5a6a013e9c958},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09649. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\chi(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*} \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, \end{equation*} and consequently \begin{equation*} \chi(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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.09649 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:17:00.188Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).