Abstract

The generalised colouring numbers col(r)(G) and wcol(r)(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(r) and a polynomial bound for the weak r-colouring number wcol(r). In particular, we show that if G excludes K-t as a minor, for some fixed t >= 4, then col(r)(G) = (t-1 2) (2r + 1) and wcol(r)(G) = (r+t-2 t-2) (t-3) (2r + 1) is an element of O(r(t-1)). In the case of graphs G of bounded genus g, we improve the bounds to col(r)(G) = (2g + 3) (2r + 1) (and even col(r)(G) = 5r + 1 if g = 0, i.e. if G is planar) and wcol(r)(G) = (2g + (r+2 2)) (2r + 1). (C) 2017 Elsevier Ltd. All rights reserved.