Le polynôme de Tutte constitue une généralisation du polynôme chromatique introduit en théorie des graphes. Nous présentons ici une extension appelée “polynôme de Tutte à points marqués”, qui est défini sur un graphe où un ou plusieurs sommets sont colorés à l’aide d’une couleur fixée. Nous obtenons un certain nombre de résultats sur ces polynômes de Tutte à points marqués, en particulier nous établissons une relation de dualité dans le cas où tous les sommets colorés sont localisés autour d’une seule face d’un réseau planaire.
The Tutte polynomial is a generalization of the chromatic polynomial of graph colorings. Here we present an extension called the rooted Tutte polynomial, which is defined on a graph where one or more vertices are colored with prescribed colors. We establish a number of results pertaining to the rooted Tutte polynomial, including a duality relation in the case that all roots reside around a single face of a planar graph.
@article{AIF_1999__49_3_1103_0,
author = {Wu, F. Y. and King, C. and Lu, W. T.},
title = {On the rooted {Tutte} polynomial},
journal = {Annales de l'Institut Fourier},
pages = {1103--1114},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1709},
mrnumber = {2000g:05077},
zbl = {0917.05038},
language = {en},
url = {http://www.numdam.org/articles/10.5802/aif.1709/}
}
TY - JOUR AU - Wu, F. Y. AU - King, C. AU - Lu, W. T. TI - On the rooted Tutte polynomial JO - Annales de l'Institut Fourier PY - 1999 SP - 1103 EP - 1114 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://www.numdam.org/articles/10.5802/aif.1709/ DO - 10.5802/aif.1709 LA - en ID - AIF_1999__49_3_1103_0 ER -
%0 Journal Article %A Wu, F. Y. %A King, C. %A Lu, W. T. %T On the rooted Tutte polynomial %J Annales de l'Institut Fourier %D 1999 %P 1103-1114 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U http://www.numdam.org/articles/10.5802/aif.1709/ %R 10.5802/aif.1709 %G en %F AIF_1999__49_3_1103_0
Wu, F. Y.; King, C.; Lu, W. T. On the rooted Tutte polynomial. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1103-1114. doi : 10.5802/aif.1709. http://www.numdam.org/articles/10.5802/aif.1709/
[1] , A determinant formula for the number of ways of coloring of a map, Ann. Math., 14 (1912), 42-46. | JFM
[2] , A contribution to the theory of chromatic polynomials, Can. J. Math., 6 (1954), 80-91. | MR | Zbl
[3] , On dichromatic polynomials, J. Comb. Theory, 2 (1967), 301-320. | MR | Zbl
[4] , Graph Theory, in Encyclopedia of Mathematics and Its Applications, Vol. 21, Addison-Wesley, Reading, Massachusetts, 1984, Chap. 9. | Zbl
[5] , The coloring of graphs, Ann. Math., 33 (1932), 688-718. | JFM | Zbl
[6] See, for example, and , A course in combinatorics, Cambridge University Press, Cambridge, 1992, p. 301. | Zbl
[7] and , Relations between the percolation and colouring problem and other graph-theoretical problems associated with regular planar lattice: some exact results for the percolation problem, Proc. Royal Soc. London A, 322 (1971), 251-280. | MR | Zbl
[8] , The matrix of chromatic joins, J. Comb. Theory B, 57 (1993), 269-288. | MR | Zbl
[9] and , Sum rule identities and the duality relation for the Potts n-point boundary correlation function, Phys. Rev. Lett., 79 (1997), 4954-4957. | MR | Zbl
[10] and , On the duality relation for correlation functions of the Potts model, J. Phys. A: Math. Gen., 31 (1998), 2823-2836. | MR | Zbl
[11] , Duality relations for Potts correlation functions, Phys. Letters A, 228 (1997), 43-47. | MR | Zbl
[12] See, for example, , The Potts Model, Rev. Mod. Phys., 54 (1982), 235-268.
[13] , Some generalized order-disorder transformations, Proc. Camb. Philos. Soc., 48 (1954), 106-109. | MR | Zbl
[14] and , On the random-cluster model I. Introduction and relation to other models, Physica, 57 (1972), 536-564.
[15] and , Duality transformation in a many-component spin model, J. Math. Phys., 17 (1976), 439-440.
Cité par Sources :
