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

Noga Alon, Nabil Kahale

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Pages346-355
Number of pages10
ISBN (Electronic)0897916638
DOIs
StatePublished - May 23 1994
Externally publishedYes
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129502
ISSN (Print)0737-8017

Other

Other26th Annual ACM Symposium on Theory of Computing, STOC 1994
CountryCanada
CityMontreal
Period5/23/945/25/94

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'A spectral technique for coloring random 3-colorable graphs (Preliminary version)'. Together they form a unique fingerprint.

Cite this