Acyclic and tree unique colourings in 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 unlike the ordinary chromatic number, the acyclic chromatic number exhibits a phase transition from sub-linear to linear growth as the edge probability increases, even in the sparse regime and obtain estimates for the critical exponent. We show that allowing for a small relaxation in the acyclic colouring condition allows for sublinear growth for all values of the edge probability exponent. We also study a generalization of unique colourings where we impose the condition that at least one vertex in any copy of a given tree has a unique colour and obtain bounds for the minimum number of colours needed for such a colouring.