A weighted graph polynomial from chromatic invariants of knots

Noble, Steven D.; Welsh, Dominic J. A.

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.

[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