Coloring random and semi-random k-Colorable graphs

A. Blum, J. Spencer

Research output: Contribution to journalArticlepeer-review


The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k ≥ 3. On the other hand, it is known that random k-colorable graphs are easy to k-color. The algorithms for coloring random k-colorable graphs require fairly high edge densities, however. In this paper we present algorithms that color randomly generated k-colorable graphs for much lower edge densities than previous approaches. In addition, to study a wider variety of graph distributions, we also present a model of graphs generated by the semi-random source of Santha and Vazirani (M. Santha and U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) that provides a smooth transition between the worst-case and random models. In this model, the graph is generated by a “noisy adversary„-an adversary whose decisions (whether or not to insert a particular edge) have some small (random) probability of being reversed. We show that even for quite low noise rates, semi-random k-colorable graphs can be optimally colored with high probability.

Original languageEnglish (US)
Pages (from-to)204-234
Number of pages31
JournalJournal of Algorithms
Issue number2
StatePublished - Sep 1995

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Coloring random and semi-random k-Colorable graphs'. Together they form a unique fingerprint.

Cite this