Chromatic polynomials Zeros, algorithms and computational complexity

This thesis studies the chromatic polynomial Z(G;q) and its generalizaton, the partition function Z(G;q,y) of the random cluster (RC) model. The main questions concern the location of the zeros of the chromatic polynomial, and the algorithmic approximation of the RC partition function.
Chapter 2 studies the chromatic zeros of series-parallel graphs and gives regions where the zeros are dense, as well as regions where there are no zeros. With the same tools we disprove a conjecture of Sokal on the location of chromatic zeros of graphs with bounded second-largest degree.
Chapter 3 establishes a relation between these chromatic zeros, and #P-hardness of approximating the RC partition function for planar graphs. For non-real q in the regions where density of chromatic zeros is proved in Chapter 2, it is proved in this Chapter that approximating Z(G;q,y) is #P-hard.
Finally Chapter 4 exhibits an efficient randomised approximation algorithm for Z(G;q,y) when y is large and q is a positive integer. For this we consider an equivalent form of Z(G;q,y) in terms of flows, and we find a fast mixing Markov chain with flows as state space.