|
|
A229048
|
|
Number of different chromatic polynomials of a simple graph with n nodes.
|
|
16
|
|
|
|
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
|
|
|
EXAMPLE
|
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)
return len({g.chromatic_polynomial() for g in graphs(n)})
(Sage) sorted({g.chromatic_polynomial() for g in graphs(n)})
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|