Colouring graphs with bounded generalized colouring number |
| |
Authors: | Xuding Zhu |
| |
Institution: | Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, 80424, Taiwan National Center for Theoretical Sciences, Taiwan |
| |
Abstract: | Given a graph G and a positive integer p, χ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 χp(G) in terms of the k-colouring number of G for k=2p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χk+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent: - (a)
- For every positive integer p, χp(G) is bounded by a constant for all G∈K.
- (b)
- For every positive integer k,
is bounded by a constant for all G∈K. It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following: - (c)
- For every positive integer q, ∇q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.
Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇q−(1/2)(G) and by showing that there is a function Fk such that . This gives an alternate proof of the equivalence of (a) and (c). |
| |
Keywords: | Generalized colouring number Tree depth Colouring of graphs Greatest reduced average degree |
本文献已被 ScienceDirect 等数据库收录! |
|