Tension polynomials of graphs
Martin Kochol · Journal of Graph Theory · 2002
Abstract The tension polynomial FG(k) of a graph G, evaluating the number of nowhere‐zero ℤk‐tensions in G, is the nontrivial divisor of the chromatic polynomial χG(k) of G, in that χG(k) = kc(G)FG(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial IG(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2r(G)FG(k)≥IG(k)≥ (r(G)+1)FG(k), where r(G)=|V(G)|−c(G), and, for every k>1, FG(k+1)≥ FG(k)˙k / (k−1) and IG(k+1)≥IG(k)˙k/(k−1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002