Why Almost All k-Colorable Graphs Are Easy to Color

Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Coloring a k-colorable graph using k colors (ka parts per thousand yen3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the uniform distribution over k-colorable graphs with n vertices and exactly cn edges, c greater than some sufficiently large constant. We rigorously show that all proper k-colorings of most such graphs lie in a single "cluster", and agree on all but a small, though constant, portion of the vertices. We also describe a polynomial time algorithm that whp finds a proper k-coloring of such a random k-colorable graph, thus asserting that most such graphs are easy to color. This should be contrasted with the setting of very sparse random graphs (which are k-colorable whp), where experimental results show some regime of edge density to be difficult for many coloring heuristics.

Original languageEnglish
Pages (from-to)523-565
Number of pages43
JournalTheory of Computing Systems
Volume46
Issue number3
DOIs
Publication statusPublished - Apr 2010

Fingerprint

Dive into the research topics of 'Why Almost All k-Colorable Graphs Are Easy to Color'. Together they form a unique fingerprint.

Cite this