Linear Versus Centred Colouring via Pseudogrids

ABSTRACT A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a linear colouring is a vertex colouring in which every (not‐necessarily induced) path contains a vertex whose colour is unique. For a graph , the centred chromatic number and the linear chromatic number denote the minimum number of distinct colours required for a centred, respectively, linear colouring of . From these definitions, it follows immediately that for every graph . The centred chromatic number is equivalent to treedepth and has been studied extensively. Much less is known about linear colouring. Kun and colleagues prove that for any graph and conjecture that . Their upper bound was subsequently improved by Czerwiński and colleagues to . The proof of both upper bounds relies on establishing a lower bound on the linear chromatic number of pseudogrids, which appear in the proof due to their critical relationship to treewidth. Specifically, Kun and colleagues prove that pseudogrids have linear chromatic number . Our main contribution is establishing a tight bound on the linear chromatic number of pseudogrids, specifically for every pseudogrid . As a consequence we improve the general bound for all graphs to . In addition, this tight bound gives further evidence in support of Kun and colleagues' conjecture (above) that the centred chromatic number (i.e., the treedepth) of any graph is upper bounded by a linear function of its linear chromatic number.