  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 the precise value
of the critical average connectivity $c_q$. Moreover, we show that below $c_q$
there exist a clustering phase $c\in [c_d,c_q]$ in which ground states
spontaneously divide into an exponential number of clusters. Furthermore, we
extended our considerations to the case of single instances showing consistent
results. This lead us to propose a new algorithm able to color in polynomial
time random graphs in the hard but colorable region, i.e when $c\in [c_d,c_q]$.
