A weighted graph polynomial from chromatic invariants of knots

Steven D. Noble; Dominic J. A. Welsh

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 1057-1087
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Noble, Steven D., and Welsh, Dominic J. A.. "A weighted graph polynomial from chromatic invariants of knots." Annales de l'institut Fourier 49.3 (1999): 1057-1087. <http://eudml.org/doc/75356>.

@article{Noble1999,
abstract = {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.},
author = {Noble, Steven D., Welsh, Dominic J. A.},
journal = {Annales de l'institut Fourier},
keywords = {knots; chromatic invariants; weighted graphs; graph polynomial},
language = {eng},
number = {3},
pages = {1057-1087},
publisher = {Association des Annales de l'Institut Fourier},
title = {A weighted graph polynomial from chromatic invariants of knots},
url = {http://eudml.org/doc/75356},
volume = {49},
year = {1999},
}

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
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 1057
EP - 1087
AB - 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.
LA - eng
KW - knots; chromatic invariants; weighted graphs; graph polynomial
UR - http://eudml.org/doc/75356
ER -

References

top
  1. [1] J.D. ANNAN, Complexity of Counting Problems, Ph.D. thesis, Oxford University, 1994. Zbl0809.05086
  2. [2] S.V. CHMUTOV, S.V. DUZHIN, S.K. LANDO, Vassiliev knot invariants: I, Introduction, Advances Soviet Math., 21 (1994), 117-126. Zbl0956.57009MR96i:57002
  3. [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. Zbl0956.57010
  4. [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. Zbl0956.57011MR96i:57004
  5. [5] G.E. FARR, A correlation inequality involving stable sets and chromatic polynomials, J. Combinatorial Theory, Series B, 58 (1993), 14-21. Zbl0733.05038MR94a:05177
  6. [6] M.R. GAREY, D.S. JOHNSON, Computers and Intractability, W.H. Freeman, New York, 1979. 
  7. [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. Zbl0499.05058MR81g:68065
  8. [8] F. JAEGER, Tutte polynomials and link polynomials, Proc. Amer. Math. Soc., 103 (1988), 647-654. Zbl0665.57006MR89i:57004
  9. [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. Zbl0747.57006MR91h:05038
  10. [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. Zbl0366.68041MR51 #14644
  11. [11] R.M. KARP, On the complexity of combinatorial problems, Networks, 5 (1975), 45-68. Zbl0324.05003MR50 #15871
  12. [12] J. LIEBERUM, Chromatic weight systems and the corresponding knot invariants, University of Strasbourg, preprint, 1996. Zbl0957.57010
  13. [13] N. LINIAL, Hard enumeration problems in geometry and combinatorics, SIAM J. Alg. Discrete Methods, 7 (1986), 331-335. Zbl0596.68041MR87e:68029
  14. [14] I.G. MACDONALD, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, Oxford University Press, New York, 1979. Zbl0487.20007MR84g:05003
  15. [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. Zbl0498.05018MR81a:05031
  16. [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. Zbl0787.05023MR1224695
  17. [17] I. SARMIENTO, Private Communication. 
  18. [18] R.P. STANLEY, A symmetric function generalisation of the chromatic polynomial of a graph, Advances in Math., 111 (1995), 166-194. Zbl0831.05027MR96b:05174
  19. [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. Zbl1061.05508MR2000c:05152
  20. [20] W.T. TUTTE, A contribution to the theory of chromatic polynomials, Canadian J. Math., 6 (1954), 80-91. Zbl0055.17101MR15,814c
  21. [21] D.J.A. WELSH, Complexity: Knots, Colourings, and Counting, London Math. Soc. Lecture Note Series, Cambridge University Press, Cambridge, 186 (1993). Zbl0799.68008MR94m:57027
  22. [22] S. WILLERTON, Review of Chmutov, Duzhin and Lando, Vassiliev knot invariants: I-III, Math. Reviews, 96i57002 (1996). 
  23. [23] S. WILLERTON, Vassiliev invariants and the Hopf algebra of chord diagrams, Proc. Cambridge Phil. Soc., 119 (1996), 55-65. Zbl0878.57013MR96h:57009

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.