Woodall's chromatic conjecture for complete bipartite minor-free graphs

Let GG be a graph, let χ(G)\chi(G) be its chromatic number, and write G⪰̸Ks,tG \not\succeq K_{s,t} when GG has no Ks,tK_{s,t} minor.

Woodall's chromatic conjecture. For every s,tNs,t \in \mathbb{N}, if GG is a graph with G⪰̸Ks,tG \not\succeq K_{s,t}, then

χ(G)s+t1.\chi(G) \le s+t-1.

This conjecture is a weakening of Hadwiger's conjecture and was independently proposed by Seymour. The source describes it as open, while noting that Woodall proved the corresponding list-colouring conjecture when s2s \le 2.

Sources & referencesView supporting material

Primary source

Raphael Steiner, “Disproof of a Conjecture by Woodall”, arXiv:2201.09115 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.