A weighted graph polynomial from chromatic invariants of knots
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1057-1087.

Motivés par les travaux de Chmutov, de Duzhin et de Lando sur les invariants de Vassiliev, nous définissons un polynôme sur les graphes avec poids qui contient, comme spécialisations, les invariants chromatiques avec poids, mais contenant également beaucoup d’autres invariants classiques dont le polynôme de Tutte et le polynôme assorti. Il donne également la généralisation de la fonction symétrique du polynôme chromatique présentée par Stanley. Nous étudions sa complexité et prouvons des résultats de dureté pour des classes très restreintes de graphes.

Motivated by the work of Chmutov, Duzhin and Lando on Vassiliev invariants, we define a polynomial on weighted graphs which contains as specialisations the weighted chromatic invariants but also contains many other classical invariants including the Tutte and matching polynomials. It also gives the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We study its complexity and prove hardness results for very restricted classes of graphs.

@article{AIF_1999__49_3_1057_0,
     author = {Noble, Steven D. and Welsh, Dominic J. A.},
     title = {A weighted graph polynomial from chromatic invariants of knots},
     journal = {Annales de l'Institut Fourier},
     pages = {1057--1087},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1706},
     zbl = {0917.05025},
     mrnumber = {2000h:05066},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1706/}
}
TY  - JOUR
AU  - Noble, Steven D.
AU  - Welsh, Dominic J. A.
TI  - A weighted graph polynomial from chromatic invariants of knots
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 1057
EP  - 1087
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.1706/
DO  - 10.5802/aif.1706
LA  - en
ID  - AIF_1999__49_3_1057_0
ER  - 
%0 Journal Article
%A Noble, Steven D.
%A Welsh, Dominic J. A.
%T A weighted graph polynomial from chromatic invariants of knots
%J Annales de l'Institut Fourier
%D 1999
%P 1057-1087
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.1706/
%R 10.5802/aif.1706
%G en
%F AIF_1999__49_3_1057_0
Noble, Steven D.; Welsh, Dominic J. A. A weighted graph polynomial from chromatic invariants of knots. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1057-1087. doi : 10.5802/aif.1706. https://aif.centre-mersenne.org/articles/10.5802/aif.1706/

[1] J.D. Annan, Complexity of Counting Problems, Ph.D. thesis, Oxford University, 1994.

[2] S.V. Chmutov, S.V. Duzhin, S.K. Lando, Vassiliev knot invariants: I, Introduction, Advances Soviet Math., 21 (1994), 117-126. | MR | Zbl

[3] S.V. Chmutov, S.V. Duzhin, S.K. Lando, Vassiliev knot invariants: II, Intersection graph for trees, Advances Soviet Math., 21 (1994), 127-134. | Zbl

[4] S.V. Chmutov, S.V. Duzhin, S.K. Lando, Vassiliev knot invariants: III, Forest algebra and weighted graphs, Advances Soviet Math., 21 (1994), 135-145. | MR | Zbl

[5] G.E. Farr, A correlation inequality involving stable sets and chromatic polynomials, J. Combinatorial Theory, Series B, 58 (1993), 14-21. | MR | Zbl

[6] M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman, New York, 1979.

[7] M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou, The complexity of colouring circular arcs and chords, SIAM J. Algebraic and Discrete Methods, 1 (1980), 216-227. | MR | Zbl

[8] F. Jaeger, Tutte polynomials and link polynomials, Proc. Amer. Math. Soc., 103 (1988), 647-654. | MR | Zbl

[9] F. Jaeger, D.L. Vertigan, D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Proc. Cambridge Phil. Soc., 108 (1990), 35-53. | MR | Zbl

[10] R.M. Karp, Reducibility among combinatorial problems, in J.W. Thatcher, R.E. Miller, eds., Complexity of Computer Computations, Plenum Press, New York, 1972. | MR | Zbl

[11] R.M. Karp, On the complexity of combinatorial problems, Networks, 5 (1975), 45-68. | MR | Zbl

[12] J. Lieberum, Chromatic weight systems and the corresponding knot invariants, University of Strasbourg, preprint, 1996. | Zbl

[13] N. Linial, Hard enumeration problems in geometry and combinatorics, SIAM J. Alg. Discrete Methods, 7 (1986), 331-335. | MR | Zbl

[14] I.G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, Oxford University Press, New York, 1979. | MR | Zbl

[15] J.G. Oxley, D.J.A. Welsh, The Tutte polynomial and percolation, in Graph Theory and Related Topics, J.A. Bondy, U.S.R. Murty, eds., Academic Press, London, 1979. | MR | Zbl

[16] J.G. Oxley, G.P. Whittle, Tutte invariants for 2-polymatroids, in Graph Structure Theory, N. Robertson, P.D. Seymour, eds., Contemp. Math., Amer. Math. Soc., 147 (1993), 9-19. | MR | Zbl

[17] I. Sarmiento, Private Communication.

[18] R.P. Stanley, A symmetric function generalisation of the chromatic polynomial of a graph, Advances in Math., 111 (1995), 166-194. | MR | Zbl

[19] R.P. Stanley, Graph colourings and related symmetric functions: ideas and applications. A description of results, interesting applications, & notable open problems, Discrete Math., 193 (1998), 267-286. | MR | Zbl

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

[21] D.J.A. Welsh, Complexity: Knots, Colourings, and Counting, London Math. Soc. Lecture Note Series, Cambridge University Press, Cambridge, 186 (1993). | MR | Zbl

[22] S. Willerton, Review of Chmutov, Duzhin and Lando, Vassiliev knot invariants: I-III, Math. Reviews, 96i57002 (1996).

[23] S. Willerton, Vassiliev invariants and the Hopf algebra of chord diagrams, Proc. Cambridge Phil. Soc., 119 (1996), 55-65. | MR | Zbl

Cité par Sources :