Computational Complexity - Research Seminar
Christian Hoffmann: A Point-to-point Reduction for the Chromatic Polynomial Revisited
Jan. 29, 2009, 10:15 a.m.
E 1 3, Room 415
The number of k-colorings of a graph G is a polynomial in k, the chromatic polynomial of G. To study the computational complexity of graph polynomials such as the chromatic polynomial, so called point-to-point reductions have been proven to be a useful tool. A point-to-point reduction for the chromatic polynomial goes back to Linial (1986). I will give a proof for this reduction which is (1) "stronger" than the standard proof and (2) similar to the proofs of seemingly different point-to-point reductions, such as the "edge thickening" reduction for the Tutte polynomial.