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},
     mrnumber = {2000h:05066},
     zbl = {0917.05025},
     language = {en},
     url = {https://www.numdam.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://www.numdam.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://www.numdam.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://www.numdam.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

  • Aliste‐Prieto, José; Martin, Jeremy L.; Wagner, Jennifer D.; Zamora, José Chromatic symmetric functions and polynomial invariants of trees, Bulletin of the London Mathematical Society, Volume 56 (2024) no. 11, p. 3452 | DOI:10.1112/blms.13144
  • Ganesan, Arunkumar; Narayanan, Narayanan; Rao, B. V. Raghavendra; Sawant, Sagar S. Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions, Discrete Mathematics, Volume 347 (2024) no. 11, p. 114162 | DOI:10.1016/j.disc.2024.114162
  • Loehr, Nicholas A.; Warrington, Gregory S. A rooted variant of Stanley's chromatic symmetric function, Discrete Mathematics, Volume 347 (2024) no. 3, p. 113805 | DOI:10.1016/j.disc.2023.113805
  • Moffatt, Iain; Thompson, Maya Deletion–contraction and the surface Tutte polynomial, European Journal of Combinatorics, Volume 118 (2024), p. 103933 | DOI:10.1016/j.ejc.2024.103933
  • Chan, William; Crew, Logan A graph polynomial from chromatic symmetric functions, Journal of Graph Theory, Volume 105 (2024) no. 4, p. 633 | DOI:10.1002/jgt.23060
  • Aliniaeifard, Farid; Wang, Victor; van Willigenburg, Stephanie Deletion-contraction for a unified Laplacian and applications, Linear Algebra and its Applications, Volume 691 (2024), p. 50 | DOI:10.1016/j.laa.2024.03.013
  • Alfaro, Carlos A.; Merino, Criel Sandpiles, Handbook of Visual, Experimental and Computational Mathematics (2023), p. 1 | DOI:10.1007/978-3-030-93954-0_10-1
  • Chang, Shu-Chiuan; Shrock, Robert Measures of spin ordering in the Potts model with a generalized external magnetic field, Physica A: Statistical Mechanics and its Applications, Volume 613 (2023), p. 128532 | DOI:10.1016/j.physa.2023.128532
  • Aliste-Prieto, José; de Mier, Anna; Orellana, Rosa; Zamora, José Marked Graphs and the Chromatic Symmetric Function, SIAM Journal on Discrete Mathematics, Volume 37 (2023) no. 3, p. 1881 | DOI:10.1137/22m148046x
  • Crew, Logan A note on distinguishing trees with the chromatic symmetric function, Discrete Mathematics, Volume 345 (2022) no. 2, p. 112682 | DOI:10.1016/j.disc.2021.112682
  • Crew, Logan; Spirkl, Sophie Modular relations of the Tutte symmetric function, Journal of Combinatorial Theory, Series A, Volume 187 (2022), p. 105572 | DOI:10.1016/j.jcta.2021.105572
  • Kazarian, Maxim Eduardovich; Lando, Sergei Konstantinovich Weight systems and invariants of graphs and embedded graphs, Russian Mathematical Surveys, Volume 77 (2022) no. 5, p. 893 | DOI:10.4213/rm10054e
  • Kazarian, Maxim Eduardovich; Lando, Sergei Konstantinovich Весовые системы и инварианты графов и вложенных графов, Успехи математических наук, Volume 77 (2022) no. 5(467), p. 131 | DOI:10.4213/rm10054
  • Liu, Pengyu A tree distinguishing polynomial, Discrete Applied Mathematics, Volume 288 (2021), p. 1 | DOI:10.1016/j.dam.2020.08.019
  • Aliste-Prieto, José; de Mier, Anna; Zamora, José On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial, Discrete Mathematics, Volume 344 (2021) no. 3, p. 112255 | DOI:10.1016/j.disc.2020.112255
  • Crew, Logan; Spirkl, Sophie A Complete Multipartite Basis for the Chromatic Symmetric Function, SIAM Journal on Discrete Mathematics, Volume 35 (2021) no. 4, p. 2647 | DOI:10.1137/20m1380314
  • Bychkov, B. S.; Kazakov, A. A.; Talalaev, D. V. Tutte polynomials of vertex-weighted graphs and group cohomology, Theoretical and Mathematical Physics, Volume 207 (2021) no. 2, p. 594 | DOI:10.1134/s0040577921050056
  • Goodall, Andrew; Litjens, Bart; Regts, Guus; Vena, Lluís A Tutte polynomial for maps II: The non-orientable case, European Journal of Combinatorics, Volume 86 (2020), p. 103095 | DOI:10.1016/j.ejc.2020.103095
  • Crew, Logan; Spirkl, Sophie A deletion–contraction relation for the chromatic symmetric function, European Journal of Combinatorics, Volume 89 (2020), p. 103143 | DOI:10.1016/j.ejc.2020.103143
  • Huryn, Jake; Chmutov, Sergei A few more trees the chromatic symmetric function can distinguish, Involve, a Journal of Mathematics, Volume 13 (2020) no. 1, p. 109 | DOI:10.2140/involve.2020.13.109
  • Awan, Jordan; Bernardi, Olivier Tutte polynomials for directed graphs, Journal of Combinatorial Theory, Series B, Volume 140 (2020), p. 192 | DOI:10.1016/j.jctb.2019.05.006
  • Thatte, Bhalchandra D. The connected partition lattice of a graph and the reconstruction conjecture, Journal of Graph Theory, Volume 93 (2020) no. 2, p. 181 | DOI:10.1002/jgt.22481
  • Chmutov, Sergei; Kazarian, Maxim; Lando, Sergei Polynomial graph invariants and the KP hierarchy, Selecta Mathematica, Volume 26 (2020) no. 3 | DOI:10.1007/s00029-020-00562-w
  • Makowsky, J.A.; Ravve, E.V.; Kotek, T. A logician's view of graph polynomials, Annals of Pure and Applied Logic, Volume 170 (2019) no. 9, p. 1030 | DOI:10.1016/j.apal.2019.04.007
  • Chbili, Nafaa Graph polynomials and symmetries, Journal of Algebra and Its Applications, Volume 18 (2019) no. 09, p. 1950172 | DOI:10.1142/s021949881950172x
  • GOODALL, ANDREW; KRAJEWSKI, THOMAS; REGTS, GUUS; VENA, LLUÍS A Tutte Polynomial for Maps, Combinatorics, Probability and Computing, Volume 27 (2018) no. 6, p. 913 | DOI:10.1017/s0963548318000081
  • Aliste-Prieto, José; Zamora, José; de Mier, Anna On graphs with the same restricted U -polynomial and the U -polynomial for rooted graphs, Electronic Notes in Discrete Mathematics, Volume 68 (2018), p. 185 | DOI:10.1016/j.endm.2018.06.032
  • Aliste-Prieto, José; de Mier, Anna; Zamora, José On trees with the same restricted U-polynomial and the Prouhet–Tarry–Escott problem, Discrete Mathematics, Volume 340 (2017) no. 6, p. 1435 | DOI:10.1016/j.disc.2016.09.019
  • Hasebe, Takahiro; Tsujie, Shuhei Order quasisymmetric functions distinguish rooted trees, Journal of Algebraic Combinatorics, Volume 46 (2017) no. 3-4, p. 499 | DOI:10.1007/s10801-017-0761-7
  • Shareshian, John; Wachs, Michelle L. Chromatic quasisymmetric functions, Advances in Mathematics, Volume 295 (2016), p. 497 | DOI:10.1016/j.aim.2015.12.018
  • Forge, David; Zaslavsky, Thomas Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs, Journal of Combinatorial Theory, Series B, Volume 118 (2016), p. 186 | DOI:10.1016/j.jctb.2015.12.010
  • Makowsky, Johann A.; Ravve, Elena V. Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Logic, Language, Information, and Computation, Volume 9803 (2016), p. 279 | DOI:10.1007/978-3-662-52921-8_18
  • Dasu, Shival; Marcolli, Matilde Potts models with magnetic field: Arithmetic, geometry, and computation, Journal of Geometry and Physics, Volume 97 (2015), p. 14 | DOI:10.1016/j.geomphys.2015.06.018
  • Aliste-Prieto, José; Zamora, José Proper caterpillars are distinguished by their chromatic symmetric function, Discrete Mathematics, Volume 315-316 (2014), p. 158 | DOI:10.1016/j.disc.2013.10.016
  • Godlin, B.; Katz, E.; Makowsky, J. A. Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas, Journal of Logic and Computation, Volume 22 (2012) no. 2, p. 237 | DOI:10.1093/logcom/exq006
  • McDonald, Leslie M.; Moffatt, Iain On the Potts Model Partition Function in an External Field, Journal of Statistical Physics, Volume 146 (2012) no. 6, p. 1288 | DOI:10.1007/s10955-012-0449-2
  • Ellis-Monaghan, Joanna A.; Moffatt, Iain The Tutte–Potts connection in the presence of an external magnetic field, Advances in Applied Mathematics, Volume 47 (2011) no. 4, p. 772 | DOI:10.1016/j.aam.2011.02.004
  • Bordewich, Magnus; Kang, Ross J. Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Automata, Languages and Programming, Volume 6755 (2011), p. 533 | DOI:10.1007/978-3-642-22006-7_45
  • Ellis-Monaghan, Joanna A.; Merino, Criel Graph Polynomials and Their Applications II: Interrelations and Interpretations, Structural Analysis of Complex Networks (2011), p. 257 | DOI:10.1007/978-0-8176-4789-6_10
  • Averbouch, Ilia; Godlin, Benny; Makowsky, J.A. An extension of the bivariate chromatic polynomial, European Journal of Combinatorics, Volume 31 (2010) no. 1, p. 1 | DOI:10.1016/j.ejc.2009.05.006
  • MERINO, CRIEL; NOBLE, STEVEN D. The Equivalence of Two Graph Polynomials and a Symmetric Function, Combinatorics, Probability and Computing, Volume 18 (2009) no. 4, p. 601 | DOI:10.1017/s0963548309009845
  • Kotek, T. On the reconstruction of graph invariants, Electronic Notes in Discrete Mathematics, Volume 34 (2009), p. 375 | DOI:10.1016/j.endm.2009.07.062
  • Derksen, Harm Symmetric and quasi-symmetric functions associated to polymatroids, Journal of Algebraic Combinatorics, Volume 30 (2009) no. 1, p. 43 | DOI:10.1007/s10801-008-0151-2
  • Kotek, T.; Makowsky, J. A.; Zilber, B. On Counting Generalized Colorings, Computer Science Logic, Volume 5213 (2008), p. 339 | DOI:10.1007/978-3-540-87531-4_25
  • Cameron, Peter J.; Jackson, Bill; Rudd, Jason D. Orbit-counting polynomials for graphs and codes, Discrete Mathematics, Volume 308 (2008) no. 5-6, p. 920 | DOI:10.1016/j.disc.2007.07.108
  • Martin, Jeremy L.; Morin, Matthew; Wagner, Jennifer D. On distinguishing trees by their chromatic symmetric functions, Journal of Combinatorial Theory, Series A, Volume 115 (2008) no. 2, p. 237 | DOI:10.1016/j.jcta.2007.05.008
  • Makowsky, J. A. Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Logic and Theory of Algorithms, Volume 5028 (2008), p. 403 | DOI:10.1007/978-3-540-69407-6_43
  • Loebl, Martin Chromatic polynomial, q-binomial counting and colored Jones function, Advances in Mathematics, Volume 211 (2007) no. 2, p. 546 | DOI:10.1016/j.aim.2006.09.001
  • Forge, David; Zaslavsky, Thomas Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements, Journal of Combinatorial Theory, Series A, Volume 114 (2007) no. 1, p. 97 | DOI:10.1016/j.jcta.2006.03.006
  • Giménez, Omer; Hliněný, Petr; Noy, Marc Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width, SIAM Journal on Discrete Mathematics, Volume 20 (2006) no. 4, p. 932 | DOI:10.1137/050645208
  • Giménez, Omer; Hliněný, Petr; Noy, Marc Computing the Tutte Polynomial on Graphs of Bounded Clique-Width, Graph-Theoretic Concepts in Computer Science, Volume 3787 (2005), p. 59 | DOI:10.1007/11604686_6
  • Lotz, Martin; Makowsky, Johann A. On the algebraic complexity of some families of coloured Tutte polynomials, Advances in Applied Mathematics, Volume 32 (2004) no. 1-2, p. 327 | DOI:10.1016/s0196-8858(03)00087-3
  • Farr, G.E. The Go polynomials of a graph, Theoretical Computer Science, Volume 306 (2003) no. 1-3, p. 1 | DOI:10.1016/s0304-3975(02)00831-9
  • Noy, Marc Graphs determined by polynomial invariants, Theoretical Computer Science, Volume 307 (2003) no. 2, p. 365 | DOI:10.1016/s0304-3975(03)00225-1
  • Maxová, Jana; Nešetřil, Jaroslav Complexity of Compatible Decompositions of Eulerian Graphs and Their Transformations, Algorithms — ESA 2002, Volume 2461 (2002), p. 711 | DOI:10.1007/3-540-45749-6_62
  • Bollobás, Béla; Pebody, Luke; Riordan, Oliver Contraction–Deletion Invariants for Graphs, Journal of Combinatorial Theory, Series B, Volume 80 (2000) no. 2, p. 320 | DOI:10.1006/jctb.2000.1988

Cité par 56 documents. Sources : Crossref