A Note on Coloring Sparse Random Graphs

Semester thesis of Christian Sommer, thanks to supervisor Konstantinos Panagiotou, paper published in Discrete Mathematics

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.

• A Note on Coloring Sparse Random Graphs, paper
• preprint
• Bibtex
  

  @article{journal/disc/sommer09,
    title = {A Note on Coloring Sparse Random Graphs},
    author = {Christian Sommer},
    journal = {Discrete Mathematics},
    volume = {50}, 
    issue = {10},
    pages = {3381--3384},
    year = {2009},
  }