The graph polynomial and the number of proper vertex coloring
Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper -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 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...