Dominating set based exact algorithms for 3-coloring

We show that the 3-colorability problem can be solved in O(n1.296)O(1.296n) time on any n  -vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2o(n)2o(n) time for graphs having minimum degree at least ω(n)ω(n) where ω(n)ω(n) is any function which goes to ∞. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2o(n)2o(n) time nor a 2o(m)2o(m) time algorithm is possible (m   denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(n1.2535)O(1.2535n) time.

Research highlights► This paper provides faster algorithms for 3-colorability of graphs with lower bounds on minimum degree. ► Also, the existence of sub-exponential time algorithms are shown to be unlikely if the lower bound on the minimum degree is a constant.