2023/11/20 by Ghurumuruhan Ganesan, Ganesan, Ghurumuruhan
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Limits and Structures in Graph Theory #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2311.11728
In this paper we study acyclic colouring in the random subgraph G of the complete graph Kn 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.