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

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},
     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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.5802/aif.1707/

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

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

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

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

  • Hefetz, Dan On two generalizations of the Alon–Tarsi polynomial method, Journal of Combinatorial Theory, Series B, Volume 101 (2011) no. 6, p. 403 | DOI:10.1016/j.jctb.2010.12.007
  • Goodall, A.J. Parity, eulerian subgraphs and the Tutte polynomial, Journal of Combinatorial Theory, Series B, Volume 98 (2008) no. 3, p. 599 | DOI:10.1016/j.jctb.2007.09.006
  • Goodall, Andrew J.; Welsh, Dominic J.A. On the Parity of Colourings and Flows, Journal of Combinatorial Theory, Series B, Volume 84 (2002) no. 2, p. 364 | DOI:10.1006/jctb.2001.2084

Cité par 3 documents. Sources : Crossref