LINEAR BOUND IN TERMS OF MAXMAXFLOW FOR THE CHROMATIC ROOTS OF SERIES-PARALLEL GRAPHS

We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow Lambda lie in the disc vertical bar q - 1 vertical bar < (Lambda - 1)/log 2. More generally, the same bound holds for the (real or complex) roots of the multivariate Tutte polynomial when the edge weights lie in the "real antiferromagnetic regime" -1 <= v(e) <= 0. For each Lambda >= 3, we exhibit a family of graphs, namely, the "leaf-joined trees", with maxmaxflow. and chromatic roots accumulating densely on the circle vertical bar q - 1 vertical bar = Lambda - 1, thereby showing that our result is within a factor 1/log 2 approximate to 1.442695 of being sharp.