Efficient Algorithms for Computing The Matching and Chromatic Polynomials for Series-Parallel Graphs

Abstract

We present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in $O(n^3)$ and $O(n^2)$ time respectively. Our algorithm for computing the matching polynomial generalizes and improves the result in $[13]$ from $O(n^3\log n)$ time for trees and the chromatic polynomial algorithm improves the result in $[18]$ from $O(n^4)$ time. The salient features of our results are the following:
Our techniques for computing the graph polynomials can be applied to certain other graph polynomials and other classes of graphs as well. Furthermore, our algorithms can also be parallelized into NC algorithms.