Why almost all k-colorable graphs are easy

Coloring a k-colorable graph using k colors (k≥ 3) 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 are clustered in one cluster, and agree on all but a small, though constant, number of vertices. We also show that some polynomial time algorithm can find a proper k-coloring of such a random k-colorable graph whp , thus asserting that most such graphs are easy. 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. One explanation for this phenomenon, backed up by partially non-rigorous analytical tools from statistical physics, is the complicated clustering of the solution space at that regime, unlike the more “regular” structure that denser graphs possess. Thus in some sense, our result rigorously supports this explanation.