A weighted graph polynomial from chromatic invariants of knots
Noble, Steven D. ; Welsh, Dominic J. A.
Annales de l'Institut Fourier, Tome 49 (1999), p. 1057-1087 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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},
     volume = {49},
     year = {1999},
     pages = {1057-1087},
     doi = {10.5802/aif.1706},
     mrnumber = {2000h:05066},
     zbl = {0917.05025},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 1057-1087. doi : 10.5802/aif.1706. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1057_0/

[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 96i:57002 | Zbl 0956.57009

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

[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 96i:57004 | Zbl 0956.57011

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

[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 81g:68065 | Zbl 0499.05058

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

[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 91h:05038 | Zbl 0747.57006

[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 51 #14644 | Zbl 0366.68041

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

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

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

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

[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 81a:05031 | Zbl 0498.05018

[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 1224695 | Zbl 0787.05023

[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 96b:05174 | Zbl 0831.05027

[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 2000c:05152 | Zbl 01525037

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

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

[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 96h:57009 | Zbl 0878.57013