The equivalence of two graph polynomials and a symmetric function

DOI10.1017/S0963548309009845MaRDI QIDQ3552515zbMATH OpenOpenAlexFDO

Authors Criel Merino, Steven D. Noble

Publication date 22 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.4793

Mathematics Subject Classification ID

Graph polynomials (05C31) Symmetric functions and generalizations (05E05) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55)

Abstract: The U-polynomial, the polychromate and the symmetric function generalization of the Tutte polynomial due to Stanley are known to be equivalent in the sense that the coefficients of any one of them can be obtained as a function of the coefficients of any other. The definition of each of these functions suggests a natural way in which to generalize them which also captures Tutte's universal V-functions as a specialization. We show that the equivalence remains true for the extended functions thus answering a question raised by Dominic Welsh.

Recommendations

• The U, V, and W polynomials
• The graph polynomials and their equivalence
• Universal Tutte polynomial
• Contraction-deletion invariants for graphs
• A symmetric function generalization of the chromatic polynomial of a graph

Cites work

• A correlation inequality involving stable set and chromatic polynomials
• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3766017 (Why is no real title available?)
• Intersection theory for graphs
• Polychromatic polynomials
• The coloring of graphs
• The polychromate and a chord diagram polynomial

Cited in

(14)

• A tree distinguishing polynomial
• Modular relations of the Tutte symmetric function
• More connections between the matching polynomial and the chromatic polynomial
• On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial
• Dual equivalence graphs revisited and the explicit Schur expansion of a family of LLT polynomials
• A logician's view of graph polynomials
• Thomas H. Brylawski (1944--2007)
• On sequences of polynomials arising from graph invariants
• The exchange graph and variations of the ratio of the two Symanzik polynomials
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• Semantic equivalence of graph polynomials definable in second order logic
• The graph polynomials and their equivalence
• The U, V, and W polynomials
• On the location of roots of graph polynomials

This page was built for publication: The equivalence of two graph polynomials and a symmetric function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3552515)