Stanley's tree-isomorphism conjecture asks whether the chromatic symmetric function distinguishes nonisomorphic trees. We give a reconstruction criterion that permits repeated leaf-component orders. For a proper tree, collapse each leaf component to its center and record its order as a vertex weight. We prove that the chromatic symmetric function reconstructs the tree whenever every nonleaf vertex of this weighted core has a weight that occurs nowhere else in the core. Repetitions among core leaves are unrestricted. The proof uses only the leading star-basis partition and the coefficients immediately above it. As a consequence, the conjecture holds for an infinite class of diameter-six trees not covered by the condition that all leaf-component orders are distinct. We also give a canonical integer-partition model for arbitrary diameter-six trees and an exact cut-partition implementation intended for further work. The unrestricted diameter-six case remains open.
Let $T$ be a tree. Stanley asked whether the chromatic symmetric function $X_T$ determines $T$ up to isomorphism. We approach this open problem by regarding $X_T$ as a polynomial in the power-sum symmetric functions $p_1, p_2, \dots$ and studying the invariant $\Phi_T = (\partial X_T/\partial p_1)|_{p_1 = 0}$. We prove...
By using constant term manipulations, we present the first polynomial-time algorithm for lattice-point counting in fixed dimension that does not rely on Barvinok's unimodular decomposition. The algorithm instead operates directly on a rational generating function in the form of a nested root average, as produced by the...
We disprove the conjecture that every tree with t leaves embeds isometrically into $\ell_\infty^{\lceil \log_2 t\rceil}$. We construct a 32-leaf tree whose least isometric $\ell_\infty$-dimension is six rather than five, and prove that every tree with at most 31 leaves attains the conjectured bound; Brigham et al. had...
We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pol...
We prove the 3-Decomposition Conjecture: every finite connected cubic loopless multigraph decomposes into a spanning tree, a 2-regular subgraph, and a matching. The proof rests on a new theorem on matching complements in subcubic graphs. Let H be a finite connected bridgeless simple graph of maximum degree three, and l...
Conlon and Lee asked for strongly dominating graphs beyond norming graphs and even paths. We construct a two-parameter family of pairwise non-isomorphic $2$-connected strongly dominating graphs that are not seminorming, and hence lie outside the two classes of examples previously identified for signed strong domination...
Shu-Yan Chen· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
