Exact algorithms for counting 3-colorings of graphs

Graph Coloring Problem, as one of the best known -complete problems, has been extensively studied by researchers in a wide range of fields, leading to many applications and theories in mathematics and computer science. In this paper, we focus on the design of exact algorithms for counting 3-colorings of a graph (denoted by #3-). Our approach is based on branch and reduce paradigm. We use the measure and conquer method to analyze the algorithms, in which we design two sets of measures (weights of vertices) intended for two distinct situations. In particular, we use the tree-width based technique to handle a special case by leveraging dynamic programming. As a result, we obtain an -time algorithm for the #3- problem, which improves the previous -time algorithm by Fomin et al. (2007).