Xuding Zhu (National Sun Yat-sen University, Kaohsiung, Taiwan)
Colouring graphs with bounded generalized colouring number
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 having tree-depth i gets at least i colours. The tree-depth of a graph H is the smallest k such that H is contained in the underlying undirected graph of the transitive closure of a branching in which every path has at most k vertices. For example, χ2 is the ordinary chromatic number, and χ3 is the star chromatic number. This talk presents an upper bound for χp(G) in terms of the k-colouring number colk(G) of G for k=2p-2. The k-colouring number is 1 plus the minimum, over all vertex orderings of G, of the maximum number of earlier vertices reachable from a single vertex v via a path of length at most k in which only the last vertex is earlier than v. For example, col1(G) is the ordinary colouring number, which is the Szekeres-Wilf upper bound on the chromatic number. Conversely, for each integer k, we also prove an upper bound for colk(G) 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 for G∈ K.
b) For every positive integer k, colk(G) is bounded for G∈ K.
Nešetřil and Ossona de Mendez proved (a) equivalent to another condition (c). We prove the equivalence of (a) and (c) directly, which gives an alternate proof of the equivalence of (a) and (c). |
