2022/05/30 by Prosenjit Bose, Bose, Prosenjit, Vida Dujmović +7 · 1 citation
Physics and Astronomy · #Color Science and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2205.15096
openalex publication_date 2022/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\DeclareMathOperator\chicenχcen\DeclareMathOperator\chilinχlin 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 G, the centred chromatic number \chicen(G) and the linear chromatic number \chilin(G) denote the minimum number of distinct colours required for a centred, respectively, linear colouring of G. From these definitions, it follows immediately that \chilin(G)≤ \chicen(G) for every graph G. The centred chromatic number is equivalent to treedepth and has been studied extensively. Much less is known about linear colouring. Kun et al [Algorithmica 83(1)] prove that \chicen(G) ≤ O(\chilin(G)190) for any graph G and conjecture that \chicen(G)≤ 2\chilin(G). Their upper bound was subsequently improved by Czerwinski et al [SIDMA 35(2)] to \chicen(G)≤O(\chilin(G)19). 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 et al prove that k× k pseudogrids have linear chromatic number Ω(√(k)). Our main contribution is establishing a tight bound on the linear chromatic number of pseudogrids, specifically \chilin(G)≥ Ω(k) for every k× k pseudogrid G. As a consequence we improve the general bound for all graphs to \chicen(G)≤ O(\chilin(G)10). In addition, this tight bound gives further evidence in support of Kun et al's conjecture (above) that the centred chromatic number of any graph is upper bounded by a linear function of its linear chromatic number.