Linear versus centred chromatic numbers

05/30/2022

∙

by   Prosenjit Bose, et al.

∙

0

∙

share

We prove that the linear chromatic number of any k× k pseudogrid is Ω(k). By an argument of Kun et al (Algorithmica, 2021), this result gives a tighter upper bound on the treedepth of a graph as a function of its linear chromatic number and gives further evidence in support of their conjecture that the treedepth of any graph is upper bounded by a linear function of its linear chromatic number.