Why almost all k-colorable graphs are easy

Опубликовано 7 сентября 2016, 16:52

Coloring a $k$-colorable graph using $k$ colors ($k\geq 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.