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

About 26 years old · traced to

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

∣z−1∣≤C klog⁡k.|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.

References

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.