login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A229048 Number of different chromatic polynomials of a simple graph with n nodes. 16

%I

%S 1,2,4,9,23,73,304,1954,23075,607507

%N Number of different chromatic polynomials of a simple graph with n nodes.

%C Partial sums of A245883. This may be proved using two facts: (i) the number of connected components of a graph is the multiplicity of the root 0 of the chromatic polynomial (thus the chromatic polynomial determines whether a graph is connected) and (ii) a disconnected graph is chromatically equivalent to some graph with an isolated vertex. The first statement is well known. For the latter statement, see p. 65 of [Dong]. - _Eric M. Schmidt_, Mar 20 2015

%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

%D F. M. Dong, K. M. Koh, and K. L. Teo. Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing Company, 2005.

%H MathWorld, <a href="http://mathworld.wolfram.com/ChromaticPolynomial.html">Chromatic Polynomial</a>

%H Eric M. Schmidt, <a href="/A229048/a229048_1.txt">The 304 polynomials for n=7</a>

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

%e The a(4) = 9 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 2x^2 - 3x^3 + x^4

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

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

%e -x^3 + x^4

%e 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 Table[Length[Union[chromPoly/@simpleSpans[n]]],{n,5}] (* _Gus Wiseman_, Nov 24 2018 *)

%o (Sage) def A229048(n): return len({g.chromatic_polynomial() for g in graphs(n)})

%o (Sage) for poly in sorted(list({g.chromatic_polynomial() for g in graphs(n)})): print(poly)

%Y Cf. A000088, A001187, A006125, A137568, A240936, A245883, A277203, A321911, A321994, A322011.

%K nonn,hard,more

%O 1,2

%A _Eric M. Schmidt_, Sep 25 2013

%E a(10) added by _Eric M. Schmidt_, Mar 20 2015

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 January 18 01:05 EST 2020. Contains 330995 sequences. (Running on oeis4.)