A weighted graph polynomial from chromatic invariants of knots

DOI10.5802/aif.1706zbMath0917.05025OpenAlexW2032968509MaRDI QIDQ1296158

Steven D. Noble, Dominic J. A. Welsh

Publication date: 12 July 1999

Published in: Annales de l'Institut Fourier (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=AIF_1999__49_3_1057_0

zbMATH Keywords

knotsweighted graphsgraph polynomialchromatic invariants

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15)

Related Items

Chromatic quasisymmetric functions, Graphs determined by polynomial invariants, A Tutte Polynomial for Maps, Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements, Plethysms of chromatic and Tutte symmetric functions, On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem, A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function, Chromatic polynomial, \(q\)-binomial counting and colored Jones function, More connections between the matching polynomial and the chromatic polynomial, A note on distinguishing trees with the chromatic symmetric function, Proper caterpillars are distinguished by their chromatic symmetric function, Order quasisymmetric functions distinguish rooted trees, Marked Graphs and the Chromatic Symmetric Function, Polynomial graph invariants and the KP hierarchy, Chromatic polynomials of 2-edge-coloured graphs, Deletion-contraction and the surface Tutte polynomial, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Measures of spin ordering in the Potts model with a generalized external magnetic field, On the Potts model partition function in an external field, A rooted variant of Stanley's chromatic symmetric function, A deletion-contraction relation for the chromatic symmetric function, A graph polynomial from chromatic symmetric functions, The Go polynomials of a graph., Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial, Symmetric functions in noncommuting variables, On the algebraic complexity of some families of coloured Tutte polynomials, Potts models with magnetic field: arithmetic, geometry, and computation, The Equivalence of Two Graph Polynomials and a Symmetric Function, A Tutte polynomial for maps. II: The non-orientable case, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Orbit-counting polynomials for graphs and codes, On distinguishing trees by their chromatic symmetric functions, A chromatic symmetric function in noncommuting variables, A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model, A logician's view of graph polynomials, A tree distinguishing polynomial, The Tutte-Potts connection in the presence of an external magnetic field, Tutte polynomials for directed graphs, On graphs with the same restricted \(U\)-polynomial and the \(U\)-polynomial for rooted graphs, Tutte polynomials of vertex-weighted graphs and group cohomology, Symmetric and quasi-symmetric functions associated to polymatroids, A few more trees the chromatic symmetric function can distinguish, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Graph polynomials and symmetries, Modular relations of the Tutte symmetric function, An extension of the bivariate chromatic polynomial, Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars, Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs, On the reconstruction of graph invariants, Contraction-deletion invariants for graphs, A Complete Multipartite Basis for the Chromatic Symmetric Function, Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A correlation inequality involving stable set and chromatic polynomials
• Chromatic weight systems and the corresponding knot invariants
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• A symmetric function generalization of the chromatic polynomial of a graph
• Hard Enumeration Problems in Geometry and Combinatorics
• Tutte Polynomials and Link Polynomials
• The Complexity of Coloring Circular Arcs and Chords
• On the Computational Complexity of Combinatorial Problems
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the computational complexity of the Jones and Tutte polynomials
• Vassiliev invariants and the Hopf algebra of chord diagrams
• A Contribution to the Theory of Chromatic Polynomials