Colouring graphs with bounded generalized colouring number

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