Improved algorithm to determine 3-colorability of graphs with the minimum degree at least 7

Abstract

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)\ge 8$ and $\delta (G)\ge 7$, respectively.

8 pages, 2 figures