Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, chi(p)(G) is the minimum number of colours needed to colour the vertices of G so that for any i <= p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for chi(p)(G) in terms of the k-colouring number col(k)(G) of G for k = 2(p-2). Conversely, for each integer k, we also prove an upper bound for col(k)(G) in terms of chi(k+2)(G). As a consequence, for a class K of graphs, the following two statements are equivalent: (a) For every positive integer p, chi(p)(G) is bounded by a constant for all G is an element of K. (b) For every positive integer k, col(k)(G) is bounded by a constant for all G is an element of K. It was proved by Nesetril and Ossona de Mendez that (a) is equivalent to the following: (c) For every positive integer q, del(q)(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G is an element of K. Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing del(q-(1/2))(G) and by showing that there is a function F(k) such that del((k-1)/2) (G) <= (col(k)(G))(k) <= F(k)(del((k-1)/2)(G)). This gives an alternate proof of the equivalence of (a) and (c). (C) 2008 Elsevier B.V. All rights reserved.