Propositions that relate a graph’s minors to its colorings are of great interest in graph theory, with famous examples including the Four Color Theorem and the Hadwiger Conjecture. In 2001, Woodall conjectured that for all \(x,y\in \mathbb {N}\) with \(x\le y\) , every graph that does not contain \(K_{x,y}\) as a minor is \((x+y-1)\) -choosable. In a remarkable result, Steiner disproved this conjecture in 2022. Steiner estimates that using his own approach, one can demonstrate counterexamples to Woodall’s conjecture only for \(x,y\) values no smaller than approximately \(10^{29}\) . By adapting Steiner’s approach, we find that counterexamples exist whenever \((x,y)=(t,t)\) for any \(t\ge 48\) with \(t\ne 49\) or \((x,y)=(t,t+1)\) for any \(t\ge 54\) with \(t\ne 55\) . Our most important modification is that when defining a random event in a probabilistic method argument, we only require a certain property to hold for subsets of a graph’s vertex set with size 1, rather than a larger size, which allows us to bound the probability of the event for much smaller graphs.
