A321979 - OEIS

%I #10 Aug 23 2023 08:43:28

%S 1,1,2,8,60,899

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

%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 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.

%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/100.pdf">A symmetric function generalization of the chromatic polynomial of a graph</a>, Advances in Math. 111 (1995), 166-194.

%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/taor.pdf">Graph colorings and related symmetric functions: ideas and applications</a>, Discrete Mathematics 193 (1998), 267-286.

%H Richard P. Stanley and John R. Stembridge, <a href="https://doi.org/10.1016/0097-3165(93)90048-D">On immanants of Jacobi-Trudi matrices and permutations with restricted position</a>, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.

%H Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.

%H Gus Wiseman, <a href="/A321979/a321979.png">The a(4) = 60 e-positive simple labeled graphs.</a>

%e The 4 non-e-positive simple labeled graphs on 4 vertices are:

%e   {{1,2},{1,3},{1,4}}

%e   {{1,2},{2,3},{2,4}}

%e   {{1,3},{2,3},{3,4}}

%e   {{1,4},{2,4},{3,4}}

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

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Nov 23 2018