Zeros of chromatic and flow polynomials of graphs (Q1402880): Difference between revisions

The chromatic polynomial \(P(G,k)\) of a graph \(G\) is the number of colorings of \(G\) using a set of \(k\) colors, when \(k\) is a natural number. Thus the chromatic number of \(G\) is the smallest natural number which is not a root of the chromatic polynomial. The present attractive paper surveys what is known about (non-integer) roots. If \(G\) is planar, then \(P(G,k)\) counts the number of nowhere zero \(k\)-flows, and this generalizes to the flow polonomial of an arbitrary graph. Roots of flow polynomials are also surveyed in this paper. Some of these results are generalized to matroids, and a number of intriguing unsolved problems are discussed.