Smallest K_{s,t}-minor Woodall counterexample

Status partial medium confidence

Steiner's 2022 disproof of Woodall's conjecture used a probabilistic argument that only yields counterexamples for astronomically large parameters (estimated around 10^29). A 2025 follow-up by Vanderbush in Graphs and Combinatorics substantially reduced this, constructing explicit counterexamples for (s,t)=(t,t) with t ≥ 48 (t ≠ 49) and (s,t)=(t,t+1) with t ≥ 54 (t ≠ 55). The question of determining the absolute smallest s and t for which the conjecture fails remains open.

Cited literature (1)

• partial New Counterexamples to a Conjecture by Woodall on Graph Minors and List Coloring (2025)
  Vanderbush · Graphs and Combinatorics · doi:10.1007/s00373-025-02957-y

  By adapting Steiner's probabilistic construction, constructs explicit counterexamples to Woodall's conjecture for (s,t)=(t,t) whenever t ≥ 48 (t ≠ 49) and (s,t)=(t,t+1) whenever t ≥ 54 (t ≠ 55), reducing the previously astronomically large parameter bounds to small explicit values.

Reviewer notes. The Springer URL for the Vanderbush (2025) paper could not be directly fetched (authentication redirect), but was consistently returned by two independent search queries with matching details. The open problem (smallest s+t for a counterexample) has significant partial progress — the bound is now explicit and small (t ≥ 48) rather than astronomical — but the exact minimum remains undetermined.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).