Thumbnail Image
Publication

Counting Subtrees Using the Chromatic Symmetric Function

Salcido, Enrique
Citations
Altmetric:
Abstract
In 1995 Richard Stanley defined the chromatic symmetric function as a generalization of the chromatic polynomial. In the same paper Stanley gave a expansion of the chromatic symmetric function in the power-sum basis for symmetric functions. This expansion is cancellation-free when the graph is question is a tree. Many graph invariants can be obtained from the chromatic symmetric function, many of which are outlined in Chapter 2. In particular, Martin, Morin, and Wagner showed in 2006 that the number of subtrees isomorphic to paths and stars can be obtained linearly from the coefficients of the chromatic symmetric function in the power-sum basis. We will use some of the techniques in Chapter 3 to show that the number of subtrees isomorphic to forks and near stars cannot be obtained linearly from the coefficients of the chromatic symmetric function.
Description
Date
2023-05-31
Journal Title
Journal ISSN
Volume Title
Publisher
University of Kansas
Collections
Theses
Show all metadata
Files
Thumbnail Image
990200_1.pdf
Adobe PDF, 313 KB
Research Projects
Organizational Units
Journal Issue
Keywords
Mathematics, Combinatorics, Graph Theory, Symmetric Functions, Trees
Citation
URI
https://hdl.handle.net/1808/35906
DOI
Embedded videos