A321979 Number of e-positive simple labeled graphs on n vertices.

1, 1, 2, 8, 60, 899

Offset

0,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 symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895). A graph is e-positive if, in the expansion of its chromatic symmetric function in terms of elementary symmetric functions, all coefficients are nonnegative.

Links

Table of n, a(n) for n=0..5.

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.

Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.

Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Gus Wiseman, The a(4) = 60 e-positive simple labeled graphs.

Example

The 4 non-e-positive simple labeled graphs on 4 vertices are:
  {{1,2},{1,3},{1,4}}
  {{1,2},{2,3},{2,4}}
  {{1,3},{2,3},{3,4}}
  {{1,4},{2,4},{3,4}}

Crossrefs

Cf. A000569, A006125, A229048, A240936, A277203, A321895, A321911, A321918, A321914, A321931, A321980, A321981, A321982.

Sequence in context: A143217 A192412 A191553 * A139017 A322012 A188324

Adjacent sequences: A321976 A321977 A321978 * A321980 A321981 A321982

Keyword

nonn,more

Author

Gus Wiseman, Nov 23 2018

Status

approved