Coloring random graphs

Martin Fürer, C. R. Subramanian

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

2 Scopus citations


We present an algorithm for coloring random 3-chromatic graphs with edge probabilities below the n-1/2 “barrier”. Our (deterministic) algorithm succeeds with high probability to 3-color a random 3-chromatic graph produced by partitioning the vertex set into three almost equal sets and selecting an edge between two vertices of different sets with probability p≥n-3/s+ɛ. The method is extended to k-chromatic graphs, succeeding with high probability for p≥n-α+ɛ with α=2k/((k-1)(k+2)) and ɛ>0. The algorithms work also for Blum’s balanced semi-random GSB(n, p, k) model where an adversary chooses the edge probability up to a small additive noise p.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsOtto Nurmi, Esko Ukkonen
PublisherSpringer Verlag
Number of pages8
ISBN (Print)9783540557067
StatePublished - 1992
Event3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 - Helsinki, Finland
Duration: Jul 8 1992Jul 10 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume621 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Coloring random graphs'. Together they form a unique fingerprint.

Cite this