Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

Melnikov's Valency Variety Problem

  • Zhanping Yang
  • Qinghou Zeng
Open at sourcePDFDOICite

Abstract

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 χ(G)≥⌈1+(2w(G)(w(G)−1))/(4w(G)(|V(G)|−w(G))+(|V(G)|−w(G)−1)2)⌉, and consequently χ(G)≥⌈(⌊ w(G)/2⌋)/(|V(G)|−w(G))⌉. 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.

Related

  1. The finite basis problem for all subvarieties of the variety V(S07)
    Mengya Yue
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. A variety of the mutual-visibility coloring problem for graphs
    Saneesh Babu, Marko Jakovac, Dorota Kuziak +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Zeros of Melnikov functions for periodically perturbed Hamiltonian systems with random coefficients
    Ali Ittayem, Erik Lundberg
    arXivPreprintarXiv licenceFull textDynamical systemsProbabilityarXiv
  4. Hierarchical Melnikov Realization: Logarithmic Factor Improvement to Hilbert Number Lower Bounds
    Chaoyang Qin, Xiaoming Sun
    arXivPreprintarXiv licenceFull textAnalysis & PDEsDynamical systemsarXiv
  5. Amply regular graphs with μ close to half the valency and group divisible designs
    Wei Jin, Jack H. Koolen, Chenhui Lv
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yang2026melnikovs,
  title = {{Melnikov's Valency Variety Problem}},
  author = {Zhanping Yang and Qinghou Zeng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.09649},
  eprint = {2610.09649},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.09649},
}
RIS
TY  - UNPB
TI  - Melnikov's Valency Variety Problem
AU  - Zhanping Yang
AU  - Qinghou Zeng
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.09649
UR  - https://arxiv.org/abs/2610.09649
AB  - 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 χ(G)≥⌈1+(2w(G)(w(G)−1))/(4w(G)(|V(G)|−w(G))+(|V(G)|−w(G)−1)^2)⌉, and consequently χ(G)≥⌈(⌊ w(G)/2⌋)/(|V(G)|−w(G))⌉. 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.
ER  -