Colouring graphs with bounded generalized colouring number

Given a graph GG and a positive integer pp, χp(G)χp(G) is the minimum number of colours needed to colour the vertices of GG so that for any i≤pi≤p, any subgraph HH of GG of tree-depth ii gets at least ii colours. This paper proves an upper bound for χp(G)χp(G) in terms of the kk-colouring number colk(G) of GG for k=2p−2k=2p−2. Conversely, for each integer kk, we also prove an upper bound for colk(G) in terms of χk+2(G)χk+2(G). As a consequence, for a class KK of graphs, the following two statements are equivalent: (a)For every positive integer pp, χp(G)χp(G) is bounded by a constant for all G∈KG∈K.(b)For every positive integer kk, colk(G) is bounded by a constant for all G∈KG∈K. It was proved by Nešetřil and Ossona de Mendez that (a) is equivalent to the following: (c)For every positive integer qq, ∇q(G)∇q(G) (the greatest reduced average density of GG with rank qq) is bounded by a constant for all G∈KG∈K. Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇q−(1/2)(G)∇q−(1/2)(G) and by showing that there is a function FkFk such that ∇(k−1)/2(G)≤(colk(G))k≤Fk(∇(k−1)/2(G)). This gives an alternate proof of the equivalence of (a) and (c).