A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring G ( n , p ) , Random Structures and Algorithms 24 (3) (2004) 259–278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying n p ≤ 1.01 . In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G n , p with the minimal number of colors and has expected linear running time, provided that n p ≤ 1.33 .