Conjecture on sublinear chromatic-root bounds for series-parallel graphs

Let GG be a finite undirected graph, let Δ(G)\Delta(G) denote its maximum degree, and let π(G,z)\pi(G,z) be its chromatic polynomial.

Series-parallel chromatic-root bound. There exists a universal constant C<C<\infty such that, for every series-parallel graph GG of maximum degree kk, every chromatic root zz lies in

z1Cklogk.|z-1|\leq C\,\frac{k}{\log k}.

The paper proves a bound of this order for generalized theta graphs and conjectures that the methods extend to arbitrary series-parallel graphs; it also remarks that an analogous statement for all planar graphs is only conceivable, not asserted.

Sources & referencesView supporting material

Primary source

Jason Brown, Carl Hickman, Alan D. Sokal and David G. Wagner, “On the chromatic roots of generalized theta graphs”, arXiv:math/0012033 (2000).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.