  Let $G$ be an $n$-vertex graph with the maximum degree $\Delta$ and the
minimum degree $\delta$. We give algorithms with complexity
$O(1.3158^{n-0.7~\Delta(G)})$ and $O(1.32^{n-0.73~\Delta(G)})$ that determines
if $G$ is 3-colorable, when $\delta(G)\geq 8$ and $\delta(G)\geq 7$,
respectively.
