Critical Exponent for the Acyclic Chromatic Number of Random Graphs

Abstract

In this paper we study acyclic colouring in the random subgraph $G$ of the complete graph $K_n$ on $n$ vertices where each edge is present with probability $p$; independent of the other edges. We show that the acyclic chromatic number exhibits a phase transition from sublinear to linear growth as the edge probability increases, even in the sparse regime and obtain estimates for the critical exponent. Next, we introduce a relaxation by allowing for a small fraction of "bad" cycles to violate the acyclic colouring condition and show that the critical exponent in this case is in fact zero, no matter how small the fraction.