Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




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.