  It was shown by Grohe et al. that nowhere dense classes of graphs admit
sparse neighbourhood covers of small degree. We show that a monotone graph
class admits sparse neighbourhood covers if and only if it is nowhere dense.
The existence of such covers for nowhere dense classes is established through
bounds on so-called weak colouring numbers.
  The core results of this paper are various lower and upper bounds on the weak
colouring numbers and other, closely related generalised colouring numbers. We
prove tight bounds for these numbers on graphs of bounded tree width. We
clarify and tighten the relation between the expansion (in the sense of
"bounded expansion" as defined by Nesetril and Ossona de Mendez) and the
various generalised colouring numbers. These upper bounds are complemented by
new, stronger exponential lower bounds on the generalised colouring numbers.
Finally, we show that computing weak r-colouring numbers is NP-complete for all
r>2.

Combinatorics