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

Voir la notice de l'article provenant de la source Numdam

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

@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},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1707},
     mrnumber = {2000i:05082},
     zbl = {0924.05027},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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  - http://geodesic.mathdoc.fr/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 http://geodesic.mathdoc.fr/articles/10.5802/aif.1707/
%R 10.5802/aif.1707
%G en
%F 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) no. 3, pp. 1089-1093. doi : 10.5802/aif.1707. http://geodesic.mathdoc.fr/articles/10.5802/aif.1707/

[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

Cité par Sources :