On the rooted Tutte polynomial
Annales de l'Institut Fourier, Volume 49 (1999) no. 3, pp. 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.

     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},
     zbl = {0917.05038},
     mrnumber = {2000g:05077},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1709/}
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  - https://aif.centre-mersenne.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 https://aif.centre-mersenne.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, Volume 49 (1999) no. 3, pp. 1103-1114. doi : 10.5802/aif.1709. https://aif.centre-mersenne.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.

Cited by Sources: