Acyclic colourings of graphs with obstructions

Abstract

Given a graph $G$, a colouring of $G$ is \emph{acyclic} if it is a proper colouring of $G$ and every cycle contains at least three colours. Its acyclic chromatic number $\ddot{I}{‡}_a(G)$ is the minimum~$k$ such that an acyclic $k$-colouring of $G$ exists. When $G$ has maximum degree $\hat{I}”$, it is known that $\ddot{I}{‡}_a(G)=\mathcal{O}(\hat{I}{”}^{4/3})$ as $\hat{I}”\to \infty$, and that $\ddot{I}{‡}_a(G)=\mathcal{O}(\sqrt{t}\cdot \hat{I}”)$ if in addition $G$ does not contain $K_{2,t}$ as a subgraph. We study the extremal value of the acyclic chromatic number in the class of graphs of maximum degree $\hat{I}”$ that do not contain some fixed subgraph $F$ on $t$ vertices. We establish that this extremal value is at most $\mathcal{O}(t^{8/3}\hat{I}{”}^{2/3})$ if $F$ is a tree, $\mathcal{O}(\sqrt{t}\cdot \hat{I}”)$ if $F$ is bipartite and can be made acyclic with the removal of one vertex, $2\hat{I}”+\mathcal{O}(t\hat{I}{”}^{2/3})$ if $F$ is an even cycle of length at least $6$, and $\mathcal{O}(t^{1/4}\hat{I}{”}^{5/4})$ if $F=K_{3,t}$. Moreover, we exhibit an infinite family of obstructions $F$ that each induces a different asymptotic behaviour for this extremal value. This is obtained with the derivation of lower bounds that come from the analysis of the acyclic chromatic number of a random graph drawn from either $G(n,p)$ or $G(n,n,p)$, that we entirely determine up to a $\mathrm{polylog}(n)$ factor. As a byproduct, we can certify that most of our results are tight up to a $\hat{I}{”}^{\mathcal{O}(1/t)}$ factor.

Published version: an extensive analysis of the acyclic chromatic number of random graphs has been added, providing tight lower bounds