  $\DeclareMathOperator{\chicen}{\chi_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{\chi_{\mathrm{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 \emph{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)\le \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)
\le \tilde{O}(\chilin(G)^{190})$ for any graph $G$ and conjecture that
$\chicen(G)\le 2\chilin(G)$. Their upper bound was subsequently improved by
Czerwinski et al [SIDMA 35(2)] to $\chicen(G)\le\tilde{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\times
k$ pseudogrids have linear chromatic number $\Omega(\sqrt{k})$. Our main
contribution is establishing a tight bound on the linear chromatic number of
pseudogrids, specifically $\chilin(G)\ge \Omega(k)$ for every $k\times k$
pseudogrid $G$. As a consequence we improve the general bound for all graphs to
$\chicen(G)\le \tilde{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.
