# Verification report — OPG-59927 (Open Problem Garden: list colourings of complete multipartite graphs with 2 big parts; the Ohba number of K_{a,b})

Verification date: 2026-10-16.

**Verdict.** The note gives a **partial answer**; every statement it makes is proved, the lower bounds of the main
theorem by a computer-assisted exhaustive search with exact certificates. The scope is as follows.
- **Settled (Theorem 1.2).** N_3(1) = 7 and N_3(2) = 9, where N_3(t) is the least b such that K_{3,b}+K_t is not
  (t+2)-choosable: K_{3,b}+K_1 is 3-choosable exactly for b ≤ 6, and K_{3,b}+K_2 is 4-choosable exactly for b ≤ 8.
  Hence (Corollary 1.3) φ(3,2) = φ(2,3) = 0, φ(3,b) = φ(b,3) = 1 for 3 ≤ b ≤ 6, = 2 for b ∈ {7, 8}, and
  φ(3,b) = φ(b,3) ≥ 3 for b ≥ 9.
- **Not new.** N_3(0) = 3 (classical); all upper bounds N_3(t) ≤ 1 + (t+2)⌈(t+2)/2⌉ (Cano, Gutknecht,
  Kappaganthula, Miller, Mudrock, Thornburgh, Graphs Combin. 42 (2026), art. 44, Theorems 8–9, for t ≥ 1);
  N_3(t) ≥ t+4 for t ≥ 1, N_4(1) ≥ 4, N_4(2) ≥ 5 (consequences of J. Zhu, X. Zhu, Canad. J. Math. 78 (2026)
  1473–1504, Theorem 1.2); N_4(1) = 4 and 5 ≤ N_4(2) ≤ 9 (Proposition 5.1, from these two papers); the case a = 2
  (Cano et al., Corollary 11); φ(3,3) = 1 (problem page); φ(3,4) = 1 (immediate from Zhu–Zhu).
- **Not found in the sources read, no novelty claimed.** The choosability of K_{3,5}+K_1, K_{3,6}+K_1, K_{3,6}+K_2,
  K_{3,7}+K_2 and K_{3,8}+K_2, i.e. N_3(1) ≥ 7 and N_3(2) ≥ 9, and with them the exact values φ(3,b) = φ(b,3) for
  5 ≤ b ≤ 8. Allagan's 2009 thesis, which treats Ohba numbers of K(m,n,1,…,1), could not be consulted and may contain
  some of them; so may Allagan–Bobga–Johnson (Congr. Numer. 225, 2015), Allagan–Johnson (Ars Combin. 119, 2015) and
  Chia–Chia (LNCS 4381, 2007), which could not be read either.
- **Open.** φ(a,b) for a, b ≥ 3 in general; φ(3,b) for b ≥ 9 (only 3 ≤ φ(3,b) ≤ b − 3 for 9 ≤ b ≤ 15);
  Conjecture 1.4, N_3(t) = 1 + (t+2)⌈(t+2)/2⌉, which is proved for t ≤ 2; for t = 3 it asserts N_3(3) = 16, and
  only 9 ≤ N_3(3) ≤ 16 is proved (the t = 3 searches are evidence without certificates).

The note is unrefereed.

## Statement checked
- **Primary source.** Open Problem Garden, "List Colourings of Complete Multipartite Graphs with 2 Big Parts",
  http://www.openproblemgarden.org/op/list_colourings_of_complete_multipartite_graphs_with_2_big_parts ; author on
  the page: Allagan, Julian; posted by Jon Noel on 12 April 2014. Read on 15 and 16 October 2026 (three fetches,
  byte-identical). Question: given a, b ≥ 2, the smallest t ≥ 0 with χ_ℓ(K_{a,b}+K_t) = χ(K_{a,b}+K_t). The page
  defines φ(a,b) as this number and lists φ(a,b) = 0 if a or b is 1, φ(2,2) = φ(2,3) = 0, φ(3,3) = φ(2,4) = 1, the
  bound φ ≤ a+b−5 from Noel–Reed–Wu, φ ≥ χ_ℓ(K_{a,b}) − 2, and Allagan's (2009) bounds for φ(a,2), a ≥ 5.
- **Corpus record.** ulamai/UnsolvedMath 1.6.0, OPG-59927 (record 3252): the statement and background reproduce the
  page; literature triage of 2026-08-17: partially solved.
- **Later literature.** Cano et al. call φ(a,b) the Ohba number τ_0(a,b) of K_{a,b} (a ≤ b); by monotonicity in t
  (their Lemmas 15–16, Lemma 2.1 of the note) their definition ("smallest N such that the joins with K_t, t ≥ N, are
  chromatic-choosable") and the page's ("smallest t") agree.

## Readings
| Reading | Answer | Where |
|---|---|---|
| "Smallest t with equality" vs "equality for all t ≥ N" | the same number (monotone in t) | Lemma 2.1, Corollary 2.3 |
| Lists of size exactly k vs at least k | the same (shrink the lists) | §1.1 |
| Order of a, b | φ(a,b) = φ(b,a) by K_{a,b} ≅ K_{b,a}; the values for φ(b,3) need only symmetry | Corollary 2.3(c), Corollary 1.3 |
| t = 0 allowed | yes; φ(3,2) = 0, N_3(0) = 3 | §5 |
| The question for all a, b | not answered; exact values only for {a,b} ∋ 3 with the other part ≤ 8, plus a = 2 from Cano et al. | §1.4, "Scope and priority" |

## Results in the paper
- **Section 2 (reductions, proved).** Lemma 2.1 (Cano et al., Lemma 15; Lemma 16 for H = K_{a,b}):
  χ_ℓ(H+K_1) ≤ χ_ℓ(H)+1. Lemma 2.2:
  monotonicity in a, b, t. Corollary 2.3: K_{a,b}+K_t is (t+2)-choosable iff b < N_a(t); φ(a,b) = min{t : b < N_a(t)}.
  Lemma 2.4 (blocking): no L-colouring iff every configuration f(S∪X) contains some L(y). Lemma 2.5: a colour common
  to X makes the graph colourable; otherwise configurations have ≥ k colours. Proposition 2.6: N_a(t) = min ν.
  Lemma 2.7: ν ≥ number of size-k configurations; ν ≥ Σ y_U for every exactly feasible dual vector (weak duality).
- **Proposition 3.1 (Cano et al., Theorems 8–9 for t ≥ 1; proof given for all k ≥ 2).** The explicit inner
  assignment with 1 + k⌈k/2⌉ blockers; N_3(t) ≤ 1 + k⌈k/2⌉. Explicit lists for k = 2, 3, 4.
- **Theorem 1.2.** Upper bounds by Proposition 3.1; lower bounds by the search of Section 4: all solutions of the
  type-vector equations (4) — 551 for t = 1, 297,955 for t = 2 (11 for t = 0) — in 125 and 27,871 orbits (5 for
  t = 0); 107 and 27,436 orbits (3) closed by Lemma 2.7(a), 18 and 435 (2) by exact dual certificates; smallest
  certified totals 15/2 and 16 (3), far above N − 1 = 6 and 8 (2).
- **Corollary 1.3** (φ table) and **Proposition 5.1** (a = 4, from print).
- **Conjecture 1.4** with the t = 3 evidence (Section 6), labelled as evidence.
- **Section 7** lists what a reader can check and how.

## Computations (programs and outputs in reproducibility/)
The lower bounds of Theorem 1.2 depend on the finite search; everything else is proved without computation.
- **Program written with the note** (`check_note.py`, standard library, about 20 s, TOTAL failures: 0): the 455
  certificates in exact rational arithmetic with its own configuration enumerator (smallest totals 3, 15/2, 16);
  11 / 551 / 297,955 type vectors (also counted by DP), 5 / 125 / 27,871 orbits; its fast count of size-k
  configurations equals a full enumeration on 12,480 vectors; the 4 / 65 / 3,775 vectors with fewer than N size-k
  configurations fall exactly into the 2 / 18 / 435 certificate orbits (no certificate orbit unused); the
  assignments of Proposition 3.1 for k = 2..6 (b = 3, 7, 9, 16, 19) and the K_{4,4}+K_1 assignment have no proper
  colouring (generic backtracking over the whole graph), and each becomes colourable when any one Y-vertex is
  removed; the φ table. A tamper test (one weight changed; one t = 2 certificate deleted) makes it fail.
- **Programs with which the results were first obtained** (`original/`): `enum_N3.py` (prove mode: 61 s for t = 2,
  45 s on the re-run of 2026-10-16, which reproduced the certificates exactly; full mode for t ≤ 1: N_3(0) = 3 with 3
  optimal orbits, N_3(1) = 7 with 2); `sat_N3.py` (CEGAR over python-sat/CaDiCaL 1.5.3; choosable answers without
  certificate: (0,3,2), (1,3,6), (2,3,8) [52 s, 12,515 nogoods], (1,4,3), (2,4,4) [968 s]; bad assignments found for
  (0,3,3), (1,3,7), (2,3,9), (3,3,16), (1,4,4); (3,3,15) stopped after about 27 min at the 4 GB memory limit,
  undecided, 53 completed iterations, 334,280 nogoods); `verify_certs.py` (all 2 + 18 + 435 certificates valid with
  the other enumerator); `crosscheck_configs.py` (configuration sets agree on 400/400 and 150/150 random inner
  assignments; ILP and SAT cover values agree on 21/21 small instances).
- **Verification run A** (`verification_run_A/`): its own generator (no symmetry reduction), bit-mask
  configurations and exact branch and bound (no LP/ILP/SAT): N_2(0,1,2) = 4, 9, 16 (Cano et al., Corollary 11),
  N_3(0,1,2) = 3, 7, 9, N_4(0) = 2, N_4(1) = 4; optimal orbits 3 / 2 / 1 for t = 0 / 1 / 2; branch and bound equal
  to an ILP oracle on 14,186 instances; 455 certificates valid with complete orbit coverage; the witnesses
  uncolourable by backtracking, every blocker needed; type-vector counts by a generating function, including
  2,586,506,581 for t = 3.
- **Verification run B** (`verification_run_B/`): its own generator (Venn refinement, no symmetry reduction) and
  integral certificates (forced size-k configurations + packing): all 297,955 vectors for t = 2 have ν ≥ 9
  (294,180 by the size-k configurations alone, 3,775 with packing, branch and bound never needed); exact ν
  histograms for t ≤ 1; N_4(1) = 4 over 31,321 vectors; detection tests with the false bounds N = 8 (t = 1) and
  N = 10 (t = 2) report exactly the optimal assignments (9 and 3 vectors; for t = 2 one orbit, that of
  Proposition 3.1); certificates valid, altered certificates rejected; the original programs re-run from a copy
  with identical outputs; t = 3 searches (7,490 equal-S vectors and 690 copy-S assignments certified ν ≥ 16; about
  5.7 million moves of a randomised local search found no state with certified bound ≤ 15).
- **Re-runs at the writing stage** (2026-10-16, from the package copy, outputs written elsewhere): `check_note.py`;
  `enum_N3.py` prove mode t = 0, 1, 2 and full mode t = 1; `verify_certs.py`; seven `sat_N3.py` cases; run A's
  `check_certs.py` (t = 2, identical output), `myN.py 3 1`, `witness_check.py`; run B's `vb_check_certs.py` (t = 2)
  and `vb_choos.py 3 1 7 ... exact`. All reproduced the recorded results.
- **Third verification run, on the written note** (`independent_run_2/`, 2026-10-16; programs written before those of
  the package were read; standard library): its own generator (vertex by vertex), orbits by a canonical form, all
  configurations, and for each of the 2 / 18 / 435 orbits with fewer than N size-k configurations an integral
  certificate (at least N configurations pairwise sharing at most k−1 colours; smallest families 3 / 7 / 12), so no
  LP is needed; 16 / 862 / 507,549 assignments up to renaming, of which 11 / 551 / 297,955 without a common
  X-colour; 5 / 125 / 27,871 orbits, 3 / 107 / 27,436 closed by Lemma 2.7(a), 4 / 65 / 3,775 vectors below N; DP
  counts including 2,586,506,581 (t = 3); the 455 certificates valid in exact arithmetic with its own enumerator
  (0 invalid; smallest totals 3, 15/2, 16; coverage of exactly its own orbits below N); the witnesses of
  Proposition 3.1 (k = 2..6), of §4.3 and of Proposition 5.1 uncolourable by backtracking, every blocker needed;
  optimal orbits 3 / 2 / 1; 31,321 of 35,775 inner 3-assignments of K_{4,b}+K_1 without a common X-colour. It then
  re-ran from the archive `check_note.py` (identical output except times), `enum_N3.py` prove mode t = 0, 1, 2
  (certificates identical) and full mode t = 0, 1 (same values; the recorded full-mode files come from an earlier
  version of the program with other key names, see the README), `--count-only` for t = 3, `verify_certs.py`, seven
  `sat_N3.py` cases, three programs of run A and two of run B: all recorded results reproduced.

## Independent verification runs
The results were first obtained with the programs in `original/`. Three independent verification runs, all
AI-assisted, followed (2026-10-16); each wrote its own programs. Runs A and B examined the first account of the
results, and neither read the other's report; the third run examined the written note (below).

| Item | Run A | Run B |
|---|---|---|
| Statement, definitions (φ = τ_0, N_a(t)) against the source and Cano et al. | CONFIRMED | CONFIRMED |
| Lemmas 2.1–2.7, symmetry, monotonicity, type vectors, the two pruning rules | CONFIRMED (re-derived) | CONFIRMED (re-derived) |
| Proposition 3.1 (construction) | CONFIRMED for all k ≥ 2; precision: Cano et al. Thms 8–9 need t ≥ 1 | CONFIRMED (k = 2..5 checked by a generic colourer) |
| N_3(0) = 3, N_3(1) = 7, N_3(2) = 9 | CONFIRMED (own exhaustive computation; 455 certificates and coverage checked) | CONFIRMED (own exhaustive computation; certificates checked; original programs re-run) |
| φ table, N_4(1) = 4 | CONFIRMED | CONFIRMED (N_4(1) directly) |
| Novelty | overstated: Zhu–Zhu missed; N_3(0) = 3 and N_4(1) = 4 not new; unread Allagan items to be named | overstated: Zhu–Zhu missed; N_4(1) = 4 and φ(3,4) = 1 not new; Chia–Chia unread |
| Conjecture (t = 3) | not tested | not contradicted (searches without certificates) |

Neither run found an error that affects a value. **Corrections required by the runs**, all applied in the note:
1. Cite Zhu–Zhu (Canad. J. Math. 78 (2026) 1473–1504; companion J. Graph Theory 104 (2023) 712–726) for
   N_3(t) ≥ t+4 (t ≥ 1), N_4(1) ≥ 4, N_4(2) ≥ 5; the best lower bound in print is t+4: §1.2, Proposition 5.1.
2. Remove N_3(0) = 3, N_4(1) = 4, φ(3,4) = 1 and the lower bounds of Cano et al. from what is not in print; restrict
   that to the choosability statements and the exact φ(3,b), φ(b,3), 5 ≤ b ≤ 8, with the qualifier "not found in
   the sources read": abstract, §1.3, §1.4, §5, "Scope and priority".
3. Name the unread sources (Allagan's thesis; Allagan–Bobga–Johnson 2015; Allagan–Johnson 2015; Chia–Chia 2007).
4. Cano et al. Theorems 8–9 assume t ≥ 1; t = 0 is classical: §3.
5. Bibliographic data: Allagan–Johnson is Zbl 1349.05098; the Axioms 2026 paper has five authors;
   arXiv:2509.16733 is Enumer. Comb. Appl. 6(1) (2026) #S2R5.
6. The stopped SAT run for (3,15): 53 completed iterations, 334,280 nogoods (§6); the empty log of an aborted run
   is not used.
7. Wording: φ(b,3) needs only symmetry; of the two optimal t = 1 orbits only one is the construction (§4.3); the
   survey states the problem with "≤".

### Third verification run (on the written note; `independent_run_2/`)
AI-assisted; it examined the final text, in which the proofs had been written anew, as if nothing had been checked.

| Item | Verdict |
|---|---|
| Statement and scope against the problem page and the corpus record | CONFIRMED (page fetched again, byte-identical to the earlier copies) |
| Lemmas 2.1–2.7, Corollary 2.3, Proposition 2.6, type vectors, the two pruning rules (counting, weak LP duality) | CONFIRMED (re-derived line by line) |
| Proposition 3.1 against Cano et al. Theorems 8 (k even) and 9 (k odd), s = 0, a = 3, l = k−1 | CONFIRMED |
| Theorem 1.2, Corollary 1.3, Table 1, Proposition 5.1 | CONFIRMED (own computation and proofs) |
| Quoted statements of Cano et al., Zhu–Zhu (both papers), the survey, zbMATH; DOIs (Crossref) | CONFIRMED, except the statement of Zhu–Zhu Theorem 1.2 (below) |
| Novelty | no earlier determination found (arXiv, zbMATH, Crossref, OpenAlex, one web search); no novelty claimed, as required |

It found no mathematical error. **Corrections required by the third run**, all applied:
1. Zhu–Zhu, Theorem 1.2: both exceptions occur only for even k (their Corollary 1.3; the companion paper, Theorem
   1.1); the note had listed K_{4,2⋆(k−1)} as an exception for every k. The conclusions drawn from the theorem were
   not affected (§1.2, Proposition 5.1).
2. Abstract: the 551 and 297,955 cases are the lists without a colour common to the part of size 3; the dual
   solutions used for t = 1, 2 are 18 and 435. §5: the 31,321 assignments are those without a colour common to X.
3. Lemma 2.1: Cano et al. Lemma 15; their Lemma 16 is the second statement for H = K_{a,b}.
4. §1.1: the problem page attributes the problem to Allagan "for the time being" and says that its first study in
   his thesis is unclear.
5. The date (16 October 2026), the record of this run (§4.3, §4.4, "Verification", searches), a remark in the README
   on the recorded full-mode outputs of `enum_N3.py`, and the docstring of `check_note.py` (old title; output
   unchanged).

## Relation to the literature, novelty and scope
- **Searches** (15 and 16 October 2026): the arXiv interface (for "Ohba number", chromatic-choosability of joins,
  of complete bipartite and of complete multipartite graphs), zbMATH ("Ohba number"; titles with "Ohba" or
  "chromatic-choosable"; complete tripartite choosability), Crossref, OpenAlex (partly refused with HTTP 429, not
  worked around), the works citing Cano et al. in Semantic Scholar, and three web searches; repeated on 16 October
  by the third run (seven arXiv queries; zbMATH "Ohba number", titles "chromatic-choosable", author Allagan;
  OpenAlex "Ohba number" and the works citing Cano et al., of which it lists none; a Crossref query; one more web
  search). No determination of τ_0(3,b) for b ≥ 5 was found.
- **Read.** The problem page; Cano et al. (arXiv v3: Sections 1–2, proofs of Theorems 6, 8 and 9, statements of
  Section 4); Zhu–Zhu, Canad. J. Math. (arXiv v2: introduction, Theorem 1.2 and corollaries; proofs not checked);
  Zhu–Zhu, J. Graph Theory (arXiv v1: abstract and introduction with Theorem 1.1); the 2026 survey of Vasudevan, Somasundaram and Narayanan (Section 11.1 lists the
  question as open, with "≤", and does not cite Cano et al.); the zbMATH review of Allagan–Johnson and the zbMATH
  summary of Allagan–Bobga–Johnson; abstracts of the Axioms 2026 paper (ch(K_{m,n}) only) and of the two works
  citing Cano et al. (Kaul–Marciaga–Mudrock; Bowdoin et al.), neither about τ_0(a,b) for a ≥ 3.
- **Not read.** Allagan's thesis (Auburn 2009, https://auetd.auburn.edu/handle/10415/1780): the repository could
  not be reached (connections refused or timed out; not worked around); its abstract, known only from secondary
  sources, concerns the choice numbers and Ohba numbers of K(m,n,1,…,1) and K(m,n,2,…,2), and the problem page cites
  it for bounds on φ(a,2), a ≥ 5. The full texts of Allagan–Bobga–Johnson and Allagan–Johnson. Chia–Chia (no
  abstract in zbMATH or Crossref; the publisher's page was not accessible). Each may contain some of the values above.
- **Scope.** Exact values only for a part of size 3 and the other part ≤ 8; no novelty or priority is claimed for
  them. This negative search is not a proof of priority.

## 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/