A079457 -id:A079457 - cp's OEIS frontend

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

1, 1, 2, 6, 20, 103, 759

Offset: 1

Gus Wiseman, Nov 21 2018

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 p 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).

			The a(4) = 6 connected chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                    m(1111)
           m(211) + m(1111)
          2m(211) + m(1111)
  m(22) + 2m(211) + m(1111)
  m(22) + 3m(211) + m(1111)
  m(31) + 3m(211) + m(1111)

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.
Gus Wiseman, A partition of connected graphs, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].

First differs from A079457 at a(7) = 759, A079457(7) = 706.

Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{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]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[chromSF/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,6}]

A123472 Number of weakly triangulated simple graphs on n unlabeled nodes.

Original entry on oeis.org

1, 2, 4, 11, 33, 146, 886, 8483, 126029, 2866876, 95717334, 4534590984

Offset: 1

N. J. A. Sloane, Oct 18 2006

All weakly triangulated graphs are perfect.

Also known as weakly chordal graphs. This sequence counts both connected and disconnected graphs. - Jim Nastos, Jul 23 2025

S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

for n in range(1, 11):
    count = 0
    for G in graphs(n):
        if G.is_weakly_chordal():
            count += 1
    print(n, count)
# Jim Nastos, Jul 25 2025

Euler transform of A079457. - Falk Hüffner, Jan 15 2016

a(10) and a(11) added using formula by Falk Hüffner, Jan 15 2016

Name clarified by Jim Nastos, Jul 23 2025

cp's OEIS Frontend

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica