Abstract. Let G 3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G 3n,p,3 with high probability, whenever p ≥ c/n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p ≥ polylog(n)/n [J. Algorithms, 19 (1995), pp. 204-234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.
REF present an algorithm that whp k-colors planted k-colorable graphs (the distribution of graphs generated by partitioning the n vertices into k equally-sized color classes, and including every edge connecting two different color classes with probability p; commonly denoted G n,p,k ) with a sufficiently large constant expected degree.
A Spectral Technique for Coloring Random 3-Colorable Graphs
SIAM Journal on Computing
Computer Science Mathematics