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



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



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


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


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

MathWorld, Chromatic Polynomial

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


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




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



def A229048(n):

    return len({g.chromatic_polynomial() for g in graphs(n)})

(Sage) sorted({g.chromatic_polynomial() for g in graphs(n)})


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




Eric M. Schmidt, Sep 25 2013


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 February 27 07:53 EST 2021. Contains 341649 sequences. (Running on oeis4.)