Linear versus centred chromatic numbers

MaRDI QIDQ6505981arXivFDO

Authors Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Mehrnoosh Javarsineh, Pat Morin

Published in arXiv

Abstract: We prove that the linear chromatic number of any $kimesk$ pseudogrid is $Omega(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.

This page was built for publication: Linear versus centred chromatic numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505981)