Abstract. We introduce a generic algorithmic technique and apply it on decision and counting versions of graph coloring. Our approach is based on the following idea: either a graph has nice (from the algorithmic point of view) properties which allow a simple recursive procedure to find the solution fast, or the pathwidth of the graph is small, which in turn can be used to find the solution by dynamic programming. By making use of this technique we obtain the fastest known exact algorithms -running in time O(1.7272 n ) for deciding if a graph is 4-colorable and -running in time O(1.6262 n ) and O(1.9464 n ) for counting the number of k-colorings for k = 3 and 4 respectively.
Fomin et al. showed an algorithm for the graph 4-coloring problem with running time O(1.7272 n ) by using the path decomposition REF .
Improved Exact Algorithms for Counting 3- and 4-Colorings
COCOON
Computer Science