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},
pages = {1103--1114},
year = {1999},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
doi = {10.5802/aif.1709},
zbl = {0917.05038},
mrnumber = {2000g:05077},
language = {en},
url = {https://aif.centre-mersenne.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 - 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, Tome 49 (1999) no. 3, pp. 1103-1114. doi: 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. | Zbl | MR
[3] , On dichromatic polynomials, J. Comb. Theory, 2 (1967), 301-320. | Zbl | MR
[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. | Zbl | JFM
[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. | Zbl | MR
[8] , The matrix of chromatic joins, J. Comb. Theory B, 57 (1993), 269-288. | Zbl | MR
[9] and , Sum rule identities and the duality relation for the Potts n-point boundary correlation function, Phys. Rev. Lett., 79 (1997), 4954-4957. | Zbl | MR
[10] and , On the duality relation for correlation functions of the Potts model, J. Phys. A: Math. Gen., 31 (1998), 2823-2836. | Zbl | MR
[11] , Duality relations for Potts correlation functions, Phys. Letters A, 228 (1997), 43-47. | Zbl | MR
[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. | Zbl | MR
[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 :
