On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor

The generalised colouring numbers colᵣ(G) and wcolᵣ(G) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r-colouring number colᵣ and a polynomial bound for the weak r-colouring number wcolᵣ. In particular, we show that if G excludes Kₜ as a minor, for some fixed t≥4, then colᵣ(G)≤t-12\,(2r+1) and wcolᵣ(G)≤r+t-2t-2·(t-3)(2r+1)(r\,t-1). In the case of graphs G of bounded genus g, we improve the bounds to colᵣ(G)≤(2g+3)(2r+1) (and even colᵣ(G)≤5r+1 if $g=0$, i.e. if G is planar) and wcolᵣ(G)≤(2g+r+22)\,(2r+1).