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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A229048 Number of different chromatic polynomials of a simple graph with n nodes. 16
1, 2, 4, 9, 23, 73, 304, 1954, 23075, 607507 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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

REFERENCES

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

LINKS

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

MathWorld, Chromatic Polynomial

Eric M. Schmidt, The 304 polynomials for n=7

EXAMPLE

From Gus Wiseman, Nov 24 2018: (Start)

The a(4) = 9 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

         2x^2 - 3x^3 + x^4

   -x +  3x^2 - 3x^3 + x^4

          x^2 - 2x^3 + x^4

                -x^3 + x^4

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

Table[Length[Union[chromPoly/@simpleSpans[n]]], {n, 5}] (* Gus Wiseman, Nov 24 2018 *)

PROG

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

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

CROSSREFS

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

Sequence in context: A058731 A291981 A326908 * A144309 A080376 A005669

Adjacent sequences:  A229045 A229046 A229047 * A229049 A229050 A229051

KEYWORD

nonn,hard,more

AUTHOR

Eric M. Schmidt, Sep 25 2013

EXTENSIONS

a(10) added by Eric M. Schmidt, Mar 20 2015

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 December 14 19:27 EST 2019. Contains 329987 sequences. (Running on oeis4.)