On the rooted Tutte polynomial
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1103-1114.

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] G.D. Birkhoff, A determinant formula for the number of ways of coloring of a map, Ann. Math., 14 (1912), 42-46. | JFM

[2] W.T. Tutte, A contribution to the theory of chromatic polynomials, Can. J. Math., 6 (1954), 80-91. | MR | Zbl

[3] W.T. Tutte, On dichromatic polynomials, J. Comb. Theory, 2 (1967), 301-320. | MR | Zbl

[4] W.T. Tutte, Graph Theory, in Encyclopedia of Mathematics and Its Applications, Vol. 21, Addison-Wesley, Reading, Massachusetts, 1984, Chap. 9. | Zbl

[5] H. Whitney, The coloring of graphs, Ann. Math., 33 (1932), 688-718. | JFM | Zbl

[6] See, for example, L.J. Van Lint and R.M. Wilson, A course in combinatorics, Cambridge University Press, Cambridge, 1992, p. 301. | Zbl

[7] H.N.V. Temperley and E.H. Lieb, 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] W.T. Tutte, The matrix of chromatic joins, J. Comb. Theory B, 57 (1993), 269-288. | MR | Zbl

[9] F.Y. Wu and H.Y. Huang, 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] W.T. Lu and F.Y. Wu, On the duality relation for correlation functions of the Potts model, J. Phys. A: Math. Gen., 31 (1998), 2823-2836. | MR | Zbl

[11] F.Y. Wu, Duality relations for Potts correlation functions, Phys. Letters A, 228 (1997), 43-47. | MR | Zbl

[12] See, for example, F.Y. Wu, The Potts Model, Rev. Mod. Phys., 54 (1982), 235-268.

[13] R.B. Potts, Some generalized order-disorder transformations, Proc. Camb. Philos. Soc., 48 (1954), 106-109. | MR | Zbl

[14] C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model I. Introduction and relation to other models, Physica, 57 (1972), 536-564.

[15] F.Y. Wu and Y.K. Wang, Duality transformation in a many-component spin model, J. Math. Phys., 17 (1976), 439-440.

Cité par Sources :