Polynomial iterative algorithms for coloring and analyzing random graphs

A. Braunstein, R. Mulet, A. Pagnani +2

We study the graph coloring problem over random graphs of finite average connectivity $c$. Given a number $q$ of available colors, we find that graphs with low connectivity admit a…