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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I thought circulant graphs of prime order could be good candidates for this search but it does not seem to be the case. $\endgroup$– Abraham GCommented Dec 20, 2018 at 14:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.)
answered Oct 12, 2010 at 19:45
-
1$\begingroup$ 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. $\endgroup$ Commented Oct 13, 2010 at 14:49
-
3$\begingroup$ 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. $\endgroup$ Commented Oct 20, 2010 at 15:09
$\begingroup$
$\endgroup$
1
This is quite an old post of mine. Subsequently, Rosa Orellana and Geoffrey Scott gave an infinite family of pairs of unicyclic graphs with the same chromatic symmetric functions [Discrete Math. 320 (2014), 1–14]. That's the best answer to this question that I know of. Stanley's original question for trees is still (frustratingly) open, so far as I know.
-
$\begingroup$ Thanks for this update! Note that you can merge two accounts together by following the instructions here mathoverflow.net/help/merging-accounts $\endgroup$– j.c.Commented Dec 20, 2018 at 18:34