A Note on Coloring Sparse Random Graphs

Christian Sommer
Discrete Mathematics, Volume 50, Issue 10 (pp. 3381-3384), 2009

Coja-Oghlan and Taraz proposed a graph coloring algorithm that has expected linear running time for random graphs with edge probability smaller or equal to 1.01/n. In this work, we develop their analysis by exploiting generating function techniques, and show that, in fact, their algorithm colors G(n,p) with the minimal number of colors and has expected linear running time, provided that the probability is smaller or equal to 1.33/n.

@article{Som09,
 title   = {A Note on Coloring Sparse Random Graphs},
 author  = {Christian Sommer},
 journal = {Discrete Mathematics},
 volume  = {50}, 
 number  = {10},
 pages   = {3381--3384},
 year    = {2009},
 url     = {http://dx.doi.org/10.1016/j.disc.2008.09.038},
 doi     = {10.1016/j.disc.2008.09.038},
}

Official version
Local version (136.8 KB)

Home → Publications → A Note on Coloring Sparse Random Graphs