On distinguishing trees by their chromatic symmetric functions

DOI10.1016/j.jcta.2007.05.008zbMath1133.05020arXivmath/0609339OpenAlexW2120707415MaRDI QIDQ2474494

Matthew Morin, Jeremy L. Martin, Jennifer D. Wagner

Publication date: 6 March 2008

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Trees (05C05) Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15)

Related Items

On an Algorithm for Comparing the Chromatic Symmetric Functions of Trees ⋮ On the \(e\)-positivity of trees and spiders ⋮ \(H\)-chromatic symmetric functions ⋮ Chromatic quasisymmetric functions ⋮ Plurigraph coloring and scheduling problems ⋮ Plethysms of chromatic and Tutte symmetric functions ⋮ On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem ⋮ Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs ⋮ A note on distinguishing trees with the chromatic symmetric function ⋮ A categorification of the chromatic symmetric function ⋮ Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves ⋮ Proper caterpillars are distinguished by their chromatic symmetric function ⋮ Graphs with equal chromatic symmetric functions ⋮ Greedy trees, subtrees and antichains ⋮ Order quasisymmetric functions distinguish rooted trees ⋮ Marked Graphs and the Chromatic Symmetric Function ⋮ Distance distributions and inverse problems for metric measure spaces ⋮ Quasisymmetric functions distinguishing trees ⋮ Tridiagonal maximum-entropy sampling and tridiagonal masks ⋮ A combinatorial formula for the Schur coefficients of chromatic symmetric functions ⋮ The amazing chromatic polynomial ⋮ A rooted variant of Stanley's chromatic symmetric function ⋮ Chromatic bases for symmetric functions ⋮ Flip graphs, Yoke graphs and diameter ⋮ The \(e\)-positivity of two classes of cycle-chord graphs ⋮ On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial ⋮ Lollipop and Lariat Symmetric Functions ⋮ Counting Markov equivalence classes for DAG models on trees ⋮ Chromatic symmetric functions of hypertrees ⋮ A tree distinguishing polynomial ⋮ Tutte polynomials for directed graphs ⋮ On graphs with the same restricted \(U\)-polynomial and the \(U\)-polynomial for rooted graphs ⋮ Extended chromatic symmetric functions and equality of ribbon Schur functions ⋮ Schur and \(e\)-positivity of trees and cut vertices ⋮ Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions ⋮ Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions ⋮ A few more trees the chromatic symmetric function can distinguish ⋮ Chromatic posets ⋮ Combinatorial Hopf Algebras of Simplicial Complexes ⋮ Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars ⋮ Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs ⋮ The \(e\)-positivity and Schur positivity of some spiders and broom trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection theory for graphs
• Brick tabloids and the connection matrices between bases of symmetric functions
• A weighted graph polynomial from chromatic invariants of knots
• The polychromate and a chord diagram polynomial
• A symmetric function generalization of the chromatic polynomial of a graph
• Trees with the same degree sequence and path numbers
• Non-isomorphic caterpillars with identical subtree data
• HOW TO COUNT TREES?
• Tutte polynomials for trees
• The Reconstruction of a Tree from its Maximal Subtrees
• A chromatic symmetric function in noncommuting variables