Dans un article précédent Alon et Tarsi ont présenté une somme pondérée sur l’ensemble des -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 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 -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 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},
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://www.numdam.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 - http://www.numdam.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 http://www.numdam.org/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://www.numdam.org/articles/10.5802/aif.1707/
[1] and , Colorings and orientations of graphs, Combinatorica, 12 (1992), 125-134. | MR | Zbl
[2] and , A note on graph colorings and graph polynomials, J. Comb. Theory, B 70 (1997), 197-201. | MR | Zbl
[3] and , A solution to a Colouring problem of P. Erdös, Discrete Math., 101 (1992), 39-48. | MR | Zbl
[4] , 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 | Zbl
Cité par Sources :
