The graph polynomial and the number of proper vertex colorings

The graph polynomial \(P_G\) of a graph \(G=(V,E)\), where \(V= \{1, \dots, n\}\), is defined as \[ \prod_{ij\in E,i<j}(x_j-x_i), \] and \(\| \overline P_G^k\|^2_2\) is defined as the number obtained by taking the remainder of \(P_G\) modulo the ideal generated by the polynomials \(x^k_i-1\), \(1 \leq i\leq n\), and then summing the squares of the coefficients. A formula for \(\| \overline P^k_G \|^2_2\) in terms of proper \(k\)-colourings of \(G\) was presented in [\textit{N. Alon} and \textit{M. Tarsi}, A note on graph colorings and graph polynomials, J. Comb. Theory, Ser. B 70, No. 1, 197-201, Art. No. TB971753 (1991; Zbl 0883.05050)]. The article under review presents another formula for \(\| \overline P^k_G \|^2_2\) in terms of partial edge-orientations of \(G\), and then compares the two formulae for \(k=3\) to prove that the number of proper 3-colourings of a graph \(G\) is congruent modulo 4 to the number of total edge-orientations of \(G\) in which every vertex has the same in-degree as out-degree. A consequence of this latter result is that the number of proper 3-colourings of a 4-regular graph \(G\) has the same parity as the number of Eulerian orientations of \(G\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: The graph polynomial and the number of proper vertex colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296159)