The graph polynomial and the number of proper vertex coloring
Tarsi, Michael
Annales de l'Institut Fourier, Tome 49 (1999), p. 1089-1093 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Dans un article précédent Alon et Tarsi ont présenté une somme pondérée sur l’ensemble des k-colorations réalisables d’un graphe, qui pouvait être calculée à partir du polynôme de ce graphe. Le sujet de cet article est une autre interprétation combinatoire de la même quantité, exprimée en terme du nombre de certains flots modulo k dans le graphe. Des relations entre les paramètres du graphe peuvent être obtenues en utilisant ces deux formules. Par exemple, le nombre de 3-colorations propres d’un graphe 4-régulier, et le nombre d’orientations eulériennes du même graphe, ont la même parité.

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.

@article{AIF_1999__49_3_1089_0,
     author = {Tarsi, Michael},
     title = {The graph polynomial and the number of proper vertex coloring},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {1089-1093},
     doi = {10.5802/aif.1707},
     mrnumber = {2000i:05082},
     zbl = {0924.05027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_1089_0}
}

Tarsi, Michael. The graph polynomial and the number of proper vertex coloring. Annales de l'Institut Fourier, Tome 49 (1999) pp. 1089-1093. doi : 10.5802/aif.1707. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1089_0/

[1] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica, 12 (1992), 125-134. | MR 93h:05067 | Zbl 0756.05049

[2] N. Alon and M. Tarsi, A note on graph colorings and graph polynomials, J. Comb. Theory, B 70 (1997), 197-201. | MR 98c:05055 | Zbl 0883.05050

[3] H. Fleischner and M. Stiebitz, A solution to a Colouring problem of P. Erdös, Discrete Math., 101 (1992), 39-48. | MR 93g:05050 | Zbl 0759.05037

[4] H. Sachs, Elementary proof of the cycle-plus-triangles theorem, in: Combinatorics, Paul Erdös is Eighty, Janos Bolyai Math. Soc., Budapest, 1993, Vol 1, 347-359. | MR 94j:05082 | Zbl 0797.05047