MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 [; 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.

share|cite|improve this question
up vote 3 down vote accepted

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.)

share|cite|improve this answer
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. [<>], 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 '10 at 14:49
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 '10 at 15:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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