@inproceedings{d9548ba174f140b99432833f59b85119,
title = "Coloring random graphs",
abstract = "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{\textquoteright}s balanced semi-random GSB(n, p, k) model where an adversary chooses the edge probability up to a small additive noise p.",
author = "Martin F{\"u}rer and Subramanian, {C. R.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 ; Conference date: 08-07-1992 Through 10-07-1992",
year = "1992",
doi = "10.1007/3-540-55706-7_24",
language = "English (US)",
isbn = "9783540557067",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "284--291",
editor = "Otto Nurmi and Esko Ukkonen",
booktitle = "Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings",
address = "Germany",
}