Before revision:  In particular, for any constants k, \Delta,\alpha>0, k-coloring for graphs with at least \alpha\cdot n vertices of degree at most \Delta can be solved in O\left(\left(2-\varepsilon\right)^n\right) time, for some \varepsilon = k, \Delta,\alpha As a consequence, for any constant k we can solve k-coloring exponentially faster than O^*(2^n) for sparse graphs.
After revision:  In particular, for any constants k, \Delta,\alpha>0, k-coloring for graphs with at least \alpha\cdot n vertices of degree at most \Delta can be computed in O\left(\left(2-\varepsilon\right)^n\right) time, for some \varepsilon = k, \Delta,\alpha As a consequence, for any constant k we can solve k-coloring exponentially faster than O^*(2^n) for sparse graphs.