Improved Exact Algorithms for Counting 3- and 4-Colorings.

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.7272n) for deciding if a graph is 4-colorablerunning in time O(1.6262n) and O(1.9464n) for counting the number of k-colorings for k = 3 and 4 respectively. [ABSTRACT FROM AUTHOR]