کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428652 | 686857 | 2011 | 5 صفحه PDF | دانلود رایگان |

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.
Journal: Information Processing Letters - Volume 111, Issue 6, 15 February 2011, Pages 251–255