# Verification report — OPG-46575 (Melnikov's valency-variety problem)

Verification date: 2026-09-29.

**Verdict.** The answer is no; the conjecture is false. For every k ≥ 3 there are k-chromatic graphs violating
χ(G) > ⌈⌊w(G)/2⌋/(n − w(G))⌉. Connected counterexamples exist as well. The smallest counterexample has 37 vertices:
a 3-chromatic graph with 30 distinct degrees and one isolated vertex. The smallest counterexample without isolated
vertices has 57 vertices, and it is connected. The inequality holds for every graph with χ ≤ 2. The note is
unrefereed.

## Statement checked
- **Primary source.** V. G. Vizing, "Some unsolved problems in graph theory", Uspekhi Mat. Nauk 23:6(144) (1968),
  117–134, p. 128. English translation: Russian Math. Surveys 23:6 (1968) 125–141, doi:10.1070/RM1968v023n06ABEH001252.
  - The scan of the Russian original was read.
  - The formula is γ(L) ≥ ]⌊w/2⌋/(n−w)[ + 1, where ]x[ is the least integer ≥ x. For an integer γ this is exactly
    χ > ⌈⌊w/2⌋/(n−w)⌉.
  - Vizing states it as Melnikov's conjectured lower bound, next to the Nettleton–Dirac upper bound
    χ ≤ n − ⌊w/2⌋.
- **Open Problem Garden, "Melnikov's valency-variety problem"** (posted 2013; importance "low"). The problem is the
  same, with a strict ">", and the page has no comments. The page also reports two things:
  - Jensen and Toft list the problem in Graph Coloring Problems (1995), p. 90.
  - Zykov (1968) reports that Melnikov showed the bound would be best possible.

  We did not see Jensen–Toft, Zykov or Dirac; these statements are quoted from the Open Problem Garden.
- **Corpus record.** ulamai/UnsolvedMath, OPG-46575 (status `open`). Its statement is identical to the Open Problem
  Garden text.

## Readings
| Reading | Refuted? | Witness |
|---|---|---|
| χ > ⌈⌊w/2⌋/(n−w)⌉ for all graphs with n ≥ 2 (Vizing, Open Problem Garden) | yes | F^(3)_3 + K_1: n = 37, w = 30, χ = 3, and ⌈15/7⌉ = 3 |
| the same, for connected graphs only | yes | F^(3)_4: n = 57, w = 46, χ = 3, and ⌈23/11⌉ = 3 |
| the same, restricted to χ = k, for any fixed k ≥ 3 | yes | F^(k)_3 + K_1 (14k − 5 vertices); F^(k)_4 (22k − 9 vertices, connected) |
| ]x[ read as "least integer > x" (a stronger requirement) | yes | the same graphs; F^(3)_3 itself would also fail |
| non-strict χ ≥ ⌈⌊w/2⌋/(n−w)⌉, which is not Vizing's formula | no | holds for n ≤ 400 (Thm 5.3 + Prop. 5.1, exact) and for each fixed χ and large n |

## Results in the paper
- **Lemma 2.1.** Melnikov's inequality is equivalent to (2χ − 1)(n − w) ≥ n − 1.
- **Theorem 1.1.** The explicit graphs F^(k)_c (k ≥ 3, c ≥ 1, a = c(c+1)/2) have these properties:
  - they are connected and k-chromatic;
  - n = (2k−1)(a+1) + c − 2 and m = n − w = a + 1, so (n−1) − (2k−1)m = c − 3.
  - F^(k)_3 attains equality.
  - F^(k)_3 plus an isolated vertex, and F^(k)_c for every c ≥ 4, are counterexamples.

  The structure is a complete k-partite core and an independent periphery with nested neighbourhoods. A
  triangular-number trick makes the degrees of the periphery class Y_2 exactly 1, …, a.
- **Theorem 1.2** (blow-up, Lemmas 4.1–4.2). There are connected k-chromatic graphs with n = t(32k−13) and m = 16t,
  so (n−1) − (2k−1)m = 3t − 1.
- **Theorem 1.3.**
  - (a) For bipartite graphs, w ≤ ⌊(2n+1)/3⌋, and this is sharp.
  - (b) For every K_{k+1}-free graph, m ≥ μ_k n − O(1) with μ_k = (2k − √(2(k−1)(2k−1)))/(3k−1). In particular
    μ_3 = (3−√5)/4 ≈ 0.19098, against 16/83 ≈ 0.19277 achieved by blow-ups and 1/5 conjectured.
  - (c) Every graph with at most 36 vertices satisfies the inequality. So does every graph without isolated vertices
    on at most 56 vertices. For 3 ≤ k ≤ 60 the least orders of k-chromatic counterexamples are 14k − 5 in general
    and 22k − 9 without isolated vertices.
  - Part (c) evaluates the proved bound of Theorem 5.3 in exact arithmetic.

## Computations (exact; scripts and outputs in reproducibility/)
- **Lead** (`lead/verify_melnikov.py`, standard library only, about 20 s). It checks:
  - F^(k)_c for 3 ≤ k ≤ 7 and 1 ≤ c ≤ 6, and their blow-ups;
  - Lemma 2.1 for n ≤ 200;
  - Prop. 5.1 on 108,622 bipartite graphs, and its sharpness example;
  - Thm 5.3 against brute force on all 33,866 labelled graphs with n ≤ 6;
  - exact exclusion for n ≤ 60 and all k, with 890 recorded certificates (s, l);
  - least orders for 3 ≤ k ≤ 60.

  Separately, `chi_check.py` finds exact chromatic numbers 3, 4, 5 and 3 for the counterexamples on 37, 51, 65 and
  57 vertices.
- **Finder** (`claimant/`).
  - The first counterexamples (37 vertices, χ = 3; 51 vertices, χ = 4) were found by a class-aware MILP followed by
    an edge MILP.
  - A SAT search found no counterexample on ≤ 20 vertices; its encoding was validated by brute force for n ≤ 7.
- **Independent referee** (`referee/`, written from the paper's text before the lead's code was read).
  - It rebuilt F^(k)_c for 3 ≤ k ≤ 7 and 1 ≤ c ≤ 7, and six blow-ups.
  - A SAT solver gave χ = k for the graphs on 36, 37, 51, 57, 65 and 79 vertices.
  - Its exact evaluation of Thm 5.3 reproduces Remark 5.4 and Thm 1.3(c), with least orders 14k−5 and 22k−9 for
    k ≤ 60.
  - It verified the algebra of Thm 1.3(b) exactly for 2 ≤ k ≤ 200.
  - A C brute force over all ≈ 2.7·10^8 labelled graphs with n ≤ 8 found no violation of Melnikov's inequality, of
    Thm 5.3 or of Prop. 5.1.
  - The lead's exported edge lists are isomorphic to the referee's graphs.

## Independent adversarial audit
Verdicts (2026-09-29):

| Item | Verdict |
|---|---|
| Statement fidelity | CONFIRMED |
| Proofs | CONFIRMED (every proof checked line by line; no mathematical error) |
| Computations | CONFIRMED |
| Answer as posed | CONFIRMED (negative) |
| Novelty | CONFIRMED as far as can be checked (no priority claim) |
| Presentation | CONFIRMED_WITH_FIXES |

All six required presentation fixes were applied:
1. The provenance of the Jensen–Toft and Zykov statements (quoted via the Open Problem Garden).
2. The web-search wording.
3. The abstract's statement of the minimal orders.
4. A proof that the bipartite bound is sharp.
5. Script and verification details.
6. A citation for the dataset record.

A remark on the non-strict variant was also added.

## Relation to the literature, novelty and scope
- **Searches (September 2026).** We searched arXiv, Crossref, OpenAlex, zbMATH and Semantic Scholar (the last was
  unreachable), and the web. Queries covered "valency-variety", distinct degrees with chromatic number, and
  Melnikov.
  - OpenAlex lists only Vizing 1968 and the Jensen–Toft chapter as citing Nettleton 1960.
  - zbMATH has only Dirac 1964 under "valency-variety".
  - Nothing reports a solution, a counterexample or a partial result beyond the Nettleton–Dirac bound.
- **Caveats.** The following were not accessed:
  - Jensen–Toft (1995);
  - Zykov's problem collection (1968);
  - Dirac (1964);
  - Russian-language follow-up literature.

  This negative search is not a proof of priority.
- **Scope.** The note refutes Melnikov's conjectured lower bound as stated. It fails by the smallest possible margin:
  the non-strict variant holds in all checked cases. Two questions remain open: the exact asymptotic constant ρ_k,
  and whether the minimal orders are 14k − 5 and 22k − 9 for every k.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/