UNI-MB - logo
UMNIK - logo
 
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • A graph polynomial from chr...
    Chan, William; Crew, Logan

    Journal of graph theory, April 2024, Letnik: 105, Številka: 4
    Journal Article

    Many graph polynomials may be derived from the coefficients of the chromatic symmetric function X G ${X}_{G}$ of a graph G $G$ when expressed in different bases. For instance, the chromatic polynomial is obtained by mapping p n → x ${p}_{n}\to x$ for each n $n$ in this function, while a polynomial whose coefficients enumerate acyclic orientations is obtained by mapping e n → x ${e}_{n}\to x$ for each n $n$. In this paper, we study a new polynomial we call the tree polynomial arising by mapping X P n → x ${X}_{{P}_{n}}\to x$, where X P n ${X}_{{P}_{n}}$ is the chromatic symmetric function of a path with n $n$ vertices. In particular, we show that this polynomial has a deletion‐contraction relation and has properties closely related to the chromatic polynomial while having coefficients that enumerate certain spanning trees and edge cutsets.