Polynomial iterative algorithms for coloring and analyzing random graphs
Polynomial iterative algorithms for coloring and analyzing random graphs
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 almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry …