Open Collections

Caterpillars, ribbons, and the chromatic symmetric function

University of British Columbia

For every n-vertex tree T, it is known that the chromatic polynomial x(T, k) is equal to k(k — l )ⁿ⁻¹. It is known that the function in noncommuting variables, Y[sub G](x), distinguishes all simple graphs. In the midground, the question of whether or not the chromatic symmetric function X[sub G](x) distinguishes nonisomorphic trees is still open. We look at Stanley's expansion of X[sub G](x) in terms of the power sum symmetric basis {pλ(x)| λ|-n) of Λⁿ , and identify properties of our trees in various coefficients of the pλ in this expansion for X[sub G](x). By restricting to the case when our tree is a caterpillar C, we shall use a correspondence between ribbons and caterpillars to look at the coefficients of the pλ(x) in the expansion of X[sub C](x) using ribbon classes. Among these ribbon classes we will have special interest in those which are symmetric. We show that the chromatic symmetric function distinguishes these symmetric classes from all other caterpillars.

Text

2009-12-23

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/17239

Mathematics

University of British Columbia

UBCV

DSpace