Before revision:  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. Thus, we link the tractability of graph coloring up to the algorithmic barrier to a single structural property. Our main theorem actually extends to coloring k-uniform hypergraphs. As such, we believe that it is an important first step towards discovering the structural properties behind the tractability of arbitrary k-CSPs for constraint densities up to the algorithmic barrier. Our main technical contribution is to prove that, for every k \ge 2, every k-uniform hypergaph of degree \Delta and girth at least 5 is efficiently (1+o(1) )(k-1) (\Delta / \ln \Delta )^{ 1/(k-1) } -list colorable via a deterministic algorithm , which is a result of independent interest .
After revision:  We prove that every k \ge 2, every k-uniform hypergaph of degree \Delta and girth at least 5 is efficiently (1+o(1) )(k-1) (\Delta / \ln \Delta )^{ 1/(k-1) } -list colorable via a deterministic algorithm , which is a result of independent interest .