7

1

Does anyone know more examples of two nonisomorphic connected graphs with the same chromatic symmetric function? The only pair I know is the one in Stanley's paper on c.s.f.'s [http://math.mit.edu/~rstan/pubs/pubfiles/100.pdf; p.5 of the PDF file]. I would especially like to have an example in which at least one of the two graphs is triangle-free.

flag

1 Answer

3

I don't think there are any other published examples. I think your best bet is to look at the literature on "chromatically equivalent graphs" (graphs with the same chromatic polynomial) and do your own computations to find examples. (I assume that you wrote some code to compute the chromatic symmetric function when you investigated trees.)

link|flag
Thanks. That keyword is helpful (and gets lots of hits on MathSciNet). I seem to remember hearing that someone came up with an infinite family of such pairs, but I lack an exact reference. BTW, the question arises from my student Brandon Humpert's quasisymmetric analogue of the c.s.f. [<arxiv.org/abs/1004.2685>], which is a generating function for a more restricted class of proper colorings (but vanishes on, among other things, non-triangle-free graphs). We are looking for a pair of graphs with the same c.s.f. that Brandon's invariant distinguishes. – Jeremy Martin Oct 13 2010 at 14:49
1 
 Update: Brandon and I cooked up an infinite family of pairs of connected graphs G,H with X(G)=X(H), by gluing together copies of the graphs in Stanley's example (the bowtie and the kite). OTOH, all these graphs of course have girth 3, so they're not useful for the purposes of studying his quasisymmetric invariant. – Jeremy Martin Oct 20 2010 at 15:09

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.