login
Number of distinct chromatic polynomials among all connected graphs on n nodes.
11

%I #30 Nov 26 2018 17:03:15

%S 1,1,2,5,14,50,231,1650,21121,584432

%N Number of distinct chromatic polynomials among all connected graphs on n nodes.

%C 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

%H Travis Hoppe and Anna Petrone, <a href="https://github.com/thoppe/Encyclopedia-of-Finite-Graphs">Encyclopedia of Finite Graphs</a>

%H T. Hoppe and A. Petrone, <a href="http://arxiv.org/abs/1408.3644">Integer sequence discovery from small graphs</a>, arXiv preprint arXiv:1408.3644 [math.CO], 2014.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticPolynomial.html">Chromatic Polynomial</a>

%e From _Gus Wiseman_, Nov 24 2018: (Start)

%e The a(4) = 5 chromatic polynomials:

%e -6x + 11x^2 - 6x^3 + x^4

%e -4x + 8x^2 - 5x^3 + x^4

%e -2x + 5x^2 - 4x^3 + x^4

%e -3x + 6x^2 - 4x^3 + x^4

%e -x + 3x^2 - 3x^3 + x^4

%e (End)

%t spsu[_,{}]:={{}};spsu[foo_,set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,___}];

%t falling[x_,k_]:=Product[(x-i),{i,0,k-1}];

%t chromPoly[g_]:=Expand[Sum[falling[x,Length[stn]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}]];

%t 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]}]];

%t 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]]]]]]]]];

%t Table[Length[Union[chromPoly/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,5}] (* _Gus Wiseman_, Nov 24 2018 *)

%Y Cf. A229048 (simple graphs, including disconnected ones, with unique chromatic polynomials).

%Y Cf. A001187, A001349, A006125, A125702, A229048, A240936, A245883, A277203, A321911, A322011.

%K nonn,hard,more

%O 1,3

%A _Travis Hoppe_ and _Anna Petrone_, Aug 05 2014