On the rooted Tutte polynomial
Wu, F. Y. ; King, C. ; Lu, W. T.
Annales de l'Institut Fourier, Tome 49 (1999), p. 1103-1114 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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},
     volume = {49},
     year = {1999},
     pages = {1103-1114},
     doi = {10.5802/aif.1709},
     mrnumber = {2000g:05077},
     zbl = {0917.05038},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 1103-1114. doi : 10.5802/aif.1709. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1103_0/

[1] G.D. Birkhoff, A determinant formula for the number of ways of coloring of a map, Ann. Math., 14 (1912), 42-46. | JFM 43.0574.02

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

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

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

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

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

[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 58 #16425 | Zbl 0211.56703

[8] W.T. Tutte, The matrix of chromatic joins, J. Comb. Theory B, 57 (1993), 269-288. | MR 94a:05144 | Zbl 0793.05030

[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 98h:82017 | Zbl 0945.82002

[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 99d:82014 | Zbl 0907.60081

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

[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 13,896c | Zbl 0048.45601

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