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

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.

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.

@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},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     pages = {1103-1114},
     doi = {10.5802/aif.1709},
     zbl = {0917.05038},
     mrnumber = {2000g:05077},
     language = {en},
     url = {http://www.numdam.org/item/AIF_1999__49_3_1103_0}
}
On the rooted Tutte polynomial. Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 1103-1114. doi : 10.5802/aif.1709. http://www.numdam.org/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.