Christian Sommer

Discrete Mathematics, Volume 50, Issue 10

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