login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A245883 Number of distinct chromatic polynomials among all connected graphs on n nodes. 11
1, 1, 2, 5, 14, 50, 231, 1650, 21121, 584432 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..10.

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

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

Sequence in context: A022562 A320954 A322725 * A115340 A298361 A000109

Adjacent sequences:  A245880 A245881 A245882 * A245884 A245885 A245886

KEYWORD

nonn,hard,more

AUTHOR

Travis Hoppe and Anna Petrone, Aug 05 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 18:55 EST 2019. Contains 329410 sequences. (Running on oeis4.)