Linear Colouring of Binomial Random Graphs

Abstract

We investigate the linear chromatic number ${\chi }_{\text{lin}}(G(n,p))$ of the binomial random graph $G(n,p)$ on $n$ vertices in which each edge appears independently with probability $p=p(n)$. For dense random graphs ($np\to \infty$ as $n\to \infty$), we show that asymptotically almost surely ${\chi }_{\text{lin}}(G(n,p))\ge n(1-O((np{)}^{-1/2}))=n(1-o(1))$. Understanding the order of the linear chromatic number for subcritical random graphs ($np<1$) and critical ones ($np=1$) is relatively easy. However, supercritical sparse random graphs ($np=c$ for some constant $c>1$) remain to be investigated.