The graph polynomial and the number of proper vertex coloring
Michael Tarsi · Annales de l’institut Fourier · 1999
Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper k -colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo k flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and the number of Eulerian orientations of that graph, have the same parity.