OFFSET
1,2
COMMENTS
A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895). - Gus Wiseman, Nov 21 2018
LINKS
Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
EXAMPLE
For n = 3, under the p basis, the CSF's are: p_{1, 1, 1}, p_{1, 1, 1} - p_{2, 1}, p_{1, 1, 1} - 2p_{2, 1} + p_{3}, p_{1, 1, 1} - 3p_{2, 1} + 2p_{3}.
From Gus Wiseman, Nov 21 2018: (Start)
The a(4) = 11 chromatic symmetric functions (m is the augmented monomial symmetric function basis):
m(1111)
m(211) + m(1111)
2m(211) + m(1111)
m(22) + 2m(211) + m(1111)
3m(211) + m(1111)
m(22) + 3m(211) + m(1111)
m(31) + 3m(211) + m(1111)
2m(22) + 4m(211) + m(1111)
m(22) + m(31) + 4m(211) + m(1111)
2m(22) + 2m(31) + 5m(211) + m(1111)
m(4) + 3m(22) + 4m(31) + 6m(211) + m(1111)
(End)
MATHEMATICA
spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsu[Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];
chromSF[g_]:=Sum[m[Sort[Length/@stn, Greater]], {stn, spsu[Select[Subsets[Union@@g], Select[DeleteCases[g, {_}], Function[ed, Complement[ed, #]=={}]]=={}&], Union@@g]}];
simpleSpans[n_]:=simpleSpans[n]=If[n==0, {{}}, Union@@Table[If[#=={}, Union[ine, {{n}}], Union[Complement[ine, List/@#], {#, n}&/@#]]&/@Subsets[Range[n-1]], {ine, simpleSpans[n-1]}]];
Table[Length[Union[chromSF/@simpleSpans[n]]], {n, 6}] (* Gus Wiseman, Nov 21 2018 *)
CROSSREFS
KEYWORD
nonn,more
STATUS
approved