Cohen-Macaulay growing graphs (Q2088715)

Let \(G\) be a simple graph and let \(A_1,\dots,A_r \subseteq V_G\), possibly empty, be such that \(A_i\cap A_j=\emptyset\), and, whenever non-empty, \(A_i\) is a clique of \(G\). The authors define a \textit{growing graph} associated to \(G\) by the additional choice of a sequence of sets of new vertices \(B_1,\dots,B_r\) (non-empty, pairwise disjoint and disjoint from \(V_G\)) and by taking the union of \(G\) with the complete graphs on \(A_i\cup B_i\). This construction is reminiscent of the operation of \textit{whiskering} introduced in [\textit{R. H. Villarreal}, Manuscr. Math. 66, No. 3, 277--293 (1990; Zbl 0737.13003)] and generalised in [\textit{D. Cook II} and \textit{U. Nagel}, SIAM J. Discrete Math. 26, No. 1, 89--101 (2012; Zbl 1245.05138)]. In one of the main results of this article (Theorem 3.5) the authors show that the independence complex of a growing graph associated to a partition of \(V_G\) into \(r\) subsets is pure shellable of dimension \(r-1\) and therefore the edge ideal of the growing graph if Cohen-Macaulay of dimension \(r\). In Corollary 3.10, the authors use the characterization of Cohen-Macaulay chordal graphs in [\textit{J. Herzog} et al., J. Comb. Theory, Ser. A 113, No. 5, 911--916 (2006; Zbl 1172.13307)] to show that any Cohen-Macaulay chordal graph is a growing graph with respect to the induced graph on the set of free vertices of the clique complex. Using the above result and also the results of [\textit{S. Ahmad} et al., J. Algebra Appl. 19, No. 3, Article ID 2050060, 11 p. (2020; Zbl 1434.13021)], the authors show that, for a chordal graph all of whose simplicial vertices are irreducible, Cohen-Macaulayness is equivalent to the grafted property of the clique complex (Theorem 4.18).