Polynomials counting group colorings in graphs

Jaeger et al. in 1992 introduced group coloring as the dual concept to group connectivity in graphs. Let A be an additive Abelian group, f : E ( G ) → A and D an orientation of a graph G . A vertex coloring c : V ( G ) → A is an ( A , f ) -coloring if c ( v ) − c ( u ) ≠ f ( e ) for each oriented edge e = u v from u to v under D . Kochol recently introduced the assigning polynomial to count nowhere-zero chains in graphs-nonhomogeneous analogues of nowhere-zero flows in Kochol (2022), and later extended the approach to regular matroids in Kochol (2024). Motivated by Kochol’s work, we define the α -compatible graph and the cycle-assigning polynomial P ( G , α ; k ) at k in terms of α -compatible spanning subgraphs, where α is an assigning of G from its cycles to { 0 , 1 } . We prove that P ( G , α ; k ) evaluates the number of ( A , f ) -colorings of G for any Abelian group A of order k and f : E ( G ) → A such that the assigning α D , f given by f equals α . Such an assigning is admissible. Based on Kochol’s work, we derive that k − c ( G ) P ( G , α ; k ) is a polynomial enumerating ( A , f ) -tensions and counting specific nowhere-zero chains. Furthermore, by extending Whitney’s broken cycle concept to broken compatible cycles, we show that the absolute value of the coefficient of k | V ( G ) | − i in P ( G , α ; k ) associated with admissible assignings α equals the number of α -compatible spanning subgraphs that have i edges and contain no broken α -compatible cycles. According to the combinatorial explanation, we establish a unified order-preserving relation from admissible assignings to cycle-assigning polynomials, and further show that for any admissible assigning α of G with α ( e ) = 1 for every loop e , the coefficients of P ( G , α ; k ) are nonzero and alternate in sign.