## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 204-234 |

Number of pages | 31 |

Journal | Journal of Algorithms |

Volume | 19 |

Issue number | 2 |

DOIs | |

State | Published - Sep 1995 |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics