no. 3
The graph polynomial and the number of proper vertex coloring
Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 1089-1093

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.

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é.

Tarsi, Michael. The graph polynomial and the number of proper vertex coloring. Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 1089-1093. doi: 10.5802/aif.1707
@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},
     pages = {1089--1093},
     year = {1999},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     doi = {10.5802/aif.1707},
     zbl = {0924.05027},
     mrnumber = {2000i:05082},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1707/}
}
TY  - JOUR
AU  - Tarsi, Michael
TI  - The graph polynomial and the number of proper vertex coloring
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 1089
EP  - 1093
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.1707/
DO  - 10.5802/aif.1707
LA  - en
ID  - AIF_1999__49_3_1089_0
ER  - 
%0 Journal Article
%A Tarsi, Michael
%T The graph polynomial and the number of proper vertex coloring
%J Annales de l'Institut Fourier
%D 1999
%P 1089-1093
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.1707/
%R 10.5802/aif.1707
%G en
%F AIF_1999__49_3_1089_0

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

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

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

[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. | Zbl | MR

Cited by Sources: