TY - GEN

T1 - A spectral technique for coloring random 3-colorable graphs (Preliminary version)

AU - Alon, Noga

AU - Kahale, Nabil

N1 - Publisher Copyright:
© 1994 ACM.

PY - 1994/5/23

Y1 - 1994/5/23

N2 - 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 an edge 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 one can design an algorithm that works almost surely for p ≥ polylog(n)/n. The algorithm can be extended to produce optimal kcolorings of random k-colorable graphs in a similar model, as well as in various related models.

AB - 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 an edge 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 one can design an algorithm that works almost surely for p ≥ polylog(n)/n. The algorithm can be extended to produce optimal kcolorings of random k-colorable graphs in a similar model, as well as in various related models.

UR - http://www.scopus.com/inward/record.url?scp=0028126125&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028126125&partnerID=8YFLogxK

U2 - 10.1145/195058.195187

DO - 10.1145/195058.195187

M3 - Conference contribution

AN - SCOPUS:0028126125

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 346

EP - 355

BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994

PB - Association for Computing Machinery

T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994

Y2 - 23 May 1994 through 25 May 1994

ER -