Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars

DOI10.4171/AIHPD/74zbMATH Open1422.05054arXiv1405.4132OpenAlexW2900383210WikidataQ123164995 ScholiaQ123164995MaRDI QIDQ2327720FDOQ2327720

Authors: Jean-Sébastien Sereni, Martin Loebl 

Publication date: 15 October 2019

Published in: Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)

Abstract: This paper contributes to a programme initiated by the first author: `How much information about a graph is revealed in its Potts partition function?'. We show that the $W$-polynomial distinguishes non-isomorphic weighted trees of a emph{good} family. The framework developed to do so also allows us to show that the $W$-polynomial distinguishes non-isomorphic caterpillars. This establishes Stanley's isomorphism conjecture for caterpillars, an extensively studied problem.

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

Recommendations

• Degrees of categoricity of trees and the isomorphism problem
• The isomorphism problem of trees from the viewpoint of Terwilliger algebras
• scientific article; zbMATH DE number 590875
• Quasi-isometries between graphs and trees
• Isomorphisms of Trees
• Greedy trees, caterpillars, and Wiener-type graph invariants
• Isomorphic factorizations of trees
• scientific article; zbMATH DE number 1556732
• Isomorphism of trees and isometry of ultrametric spaces
• Potential isomorphism and semi-proper trees

zbMATH Keywords

treegraph isomorphismgraph reconstruction\(U\)-polynomial\(W\)-polynomialPotts partition functionStanley's isomorphism conjecture

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Intersection theory for graphs
• A weighted graph polynomial from chromatic invariants of knots
• A symmetric function generalization of the chromatic polynomial of a graph
• On distinguishing trees by their chromatic symmetric functions
• Graph Classes: A Survey
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Proper caterpillars are distinguished by their chromatic symmetric function
• Graphs with equal chromatic symmetric functions
• The Potts model and chromatic functions of graphs
• Chromatic polynomial, \(q\)-binomial counting and colored Jones function
• Title not available (Why is that?)

Cited In (21)

• Proper \(q\)-caterpillars are distinguished by their chromatic symmetric functions
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• Schur and \(e\)-positivity of trees and cut vertices
• On the smallest trees with the same restricted \(U\)-polynomial and the rooted \(U\)-polynomial
• Non-isomorphic caterpillars with identical subtree data
• Marked Graphs and the Chromatic Symmetric Function
• Tutte polynomials for directed graphs
• A rooted variant of Stanley's chromatic symmetric function
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• A deletion-contraction relation for the chromatic symmetric function
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• The chromatic symmetric function of a graph centred at a vertex
• Quasisymmetric functions distinguishing trees
• A note on distinguishing trees with the chromatic symmetric function
• Chromatic symmetric functions and polynomial invariants of trees
• Quasysimmetric invariants for families of posets
• Degrees of categoricity of trees and the isomorphism problem
• A tree distinguishing polynomial
• A few more trees the chromatic symmetric function can distinguish
• A class of trees determined by their chromatic symmetric functions

This page was built for publication: Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars

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