OFFSET
1,3
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 polynomial is given by chi_G(x) = Sum_p (x)_k, where the sum is over all stable partitions of G, k is the length (number of blocks) of p, and (x)_k is the falling factorial x(x-1)(x-2)...(x-k+1). - Gus Wiseman, Nov 24 2018
LINKS
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Chromatic Polynomial
EXAMPLE
From Gus Wiseman, Nov 24 2018: (Start)
The a(4) = 5 chromatic polynomials:
-6x + 11x^2 - 6x^3 + x^4
-4x + 8x^2 - 5x^3 + x^4
-2x + 5x^2 - 4x^3 + x^4
-3x + 6x^2 - 4x^3 + x^4
-x + 3x^2 - 3x^3 + x^4
(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, ___}];
falling[x_, k_]:=Product[(x-i), {i, 0, k-1}];
chromPoly[g_]:=Expand[Sum[falling[x, Length[stn]], {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]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[chromPoly/@Select[simpleSpans[n], Length[csm[#]]==1&]]], {n, 5}] (* Gus Wiseman, Nov 24 2018 *)
CROSSREFS
Cf. A229048 (simple graphs, including disconnected ones, with unique chromatic polynomials).
KEYWORD
nonn,hard,more
AUTHOR
Travis Hoppe and Anna Petrone, Aug 05 2014
STATUS
approved