A deletion-contraction relation for the chromatic symmetric function

DOI10.1016/J.EJC.2020.103143MaRDI QIDQ2198977zbMATH OpenOpenAlexFDO

Authors Logan Crew, Sophie Spirkl

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

deletion-contraction relationsvertex-weighted graphs.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Symmetric functions and generalizations (05E05)

Abstract: We extend the definition of the chromatic symmetric function $X_G$ to include graphs $G$ with a vertex-weight function $w:V(G)ightarrowmathbbN$. We show how this provides the chromatic symmetric function with a natural deletion-contraction relation analogous to that of the chromatic polynomial. Using this relation we derive new properties of the chromatic symmetric function, and we give alternate proofs of many fundamental properties of $X_G$.

Recommendations

• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• A symmetric function generalization of the chromatic polynomial of a graph
• A chromatic symmetric function in noncommuting variables
• A quasisymmetric function generalization of the chromatic symmetric function
• Plethysms of chromatic and Tutte symmetric functions

Cites work

• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Acyclic orientations of graphs
• Chromatic bases for symmetric functions
• Chromatic polynomials of partition systems
• Chromatic quasisymmetric functions
• Chromatic quasisymmetric functions of directed graphs
• Chromatic symmetric functions in noncommuting variables revisited
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Cohomology classes of interval positroid varieties and a conjecture of Liu
• Double posets and the antipode of QSym
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Graphs with equal chromatic symmetric functions
• Hook coefficients of chromatic functions
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• LLT polynomials, chromatic quasisymmetric functions and graphs with cycles
• Lollipop and lariat symmetric functions
• On \(e\)-positivity and \(e\)-unimodality of chromatic quasisymmetric functions
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• Schur and \(e\)-positivity of trees and cut vertices
• The path-cycle symmetric function of a digraph
• Umbral interpolation and the addition/contraction tree for graphs

Cited in

(32)

• A symmetric function generalization of the chromatic polynomial of a graph
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• Modular relations of the Tutte symmetric function
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• \(H\)-chromatic symmetric functions
• Plethysms of chromatic and Tutte symmetric functions
• Chromatic symmetric functions from the modular law
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• A note on distinguishing trees with the chromatic symmetric function
• scientific article; zbMATH DE number 6704650 (Why is no real title available?)
• On graph invariants satisfying the deletion-contraction formula
• A complete multipartite basis for the chromatic symmetric function
• A chromatic symmetric function in noncommuting variables
• Marked Graphs and the Chromatic Symmetric Function
• A deletion-contraction long exact sequence for chromatic symmetric homology
• Horizontal-strip LLT polynomials
• A rooted variant of Stanley's chromatic symmetric function
• A graph polynomial from chromatic symmetric functions
• A horizontal-strip LLT polynomial is determined by its weighted graph
• A class of trees determined by their chromatic symmetric functions
• Homogeneous sets in graphs and a chromatic multisymmetric function
• An extension of Stanley's symmetric acyclicity theorem to signed graphs
• The chromatic symmetric function in the star-basis
• A signed e-expansion of the chromatic quasisymmetric function
• The kromatic symmetric function: a K-theoretic analogue of X_G
• Horizontal-strip LLT polynomials
• On graphs with equal and different Kromatic symmetric functions
• Chromatic MacMahon symmetric functions of graphs
• A weighted Murnaghan-Nakayama rule for (P, )-partitions
• A signed e-expansion of the chromatic symmetric function and some new e-positive graphs
• On the reconstruction of trees from their chromatic symmetric functions

This page was built for publication: A deletion-contraction relation for the chromatic symmetric function

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