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

DOI10.4171/AIHPD/74MaRDI QIDQ2327720zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

\(U\)-polynomial\(W\)-polynomialgraph isomorphismgraph reconstructionPotts partition functionStanley's isomorphism conjecturetree

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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 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 conjecture for caterpillars, an extensively studied problem.

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

Cites work

• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Chromatic polynomial, \(q\)-binomial counting and colored Jones function
• Graph Classes: A Survey
• 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
• scientific article; zbMATH DE number 475578 (Why is no real title available?)
• Intersection theory for graphs
• On distinguishing trees by their chromatic symmetric functions
• Proper caterpillars are distinguished by their chromatic symmetric function
• The Potts model and chromatic functions of graphs

Cited in

(27)

• A tree distinguishing polynomial
• Extended chromatic symmetric functions and equality of ribbon Schur functions
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• A deletion-contraction relation for the chromatic symmetric function
• On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial
• Tutte polynomials for directed graphs
• Schur and \(e\)-positivity of trees and cut vertices
• A few more trees the chromatic symmetric function can distinguish
• Non-isomorphic caterpillars with identical subtree data
• 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 1029230 (Why is no real title available?)
• Degrees of categoricity of trees and the isomorphism problem
• Marked Graphs and the Chromatic Symmetric Function
• Quasisymmetric functions distinguishing trees
• A rooted variant of Stanley's chromatic symmetric function
• A class of trees determined by their chromatic symmetric functions
• Proper q-caterpillars are distinguished by their chromatic symmetric functions
• The chromatic symmetric function of a graph centred at a vertex
• Quasysimmetric invariants for families of posets
• Chromatic symmetric functions and polynomial invariants of trees
• The chromatic symmetric function in the star-basis
• Distinguishing and reconstructing directed graphs by their B-polynomials
• On graphs with equal and different Kromatic symmetric functions
• Chromatic MacMahon symmetric functions of graphs
• The chromatic symmetric function for unicyclic graphs

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)