Before revision:  We answer this question positively for graph coloring by identifying the property ofgirth-reducibility . We prove that every girth-reducible graph of average degree (1-o(1) )q \ln q is efficiently q-colorable and that the threshold for girth reducibility of random graphs coincides with the algorithmic barrier.
After revision:  We answer this question positively for graph coloring by identifying the property ofgirth-reducibility We show that, for every girth-reducible graph of average degree (1-o(1) )q \ln q is efficiently q-colorable and that the threshold for girth reducibility of random graphs coincides with the algorithmic barrier.