Matchings, coverings, and Castelnuovo-Mumford regularity (Q405389): Difference between revisions

Let \(G\) be a graph on the vertex set \([n]\), \(K\) be a field and \(R=K[x_1,\ldots,x_n]\) be a polynomial ring. The edge ideal of \(G\) is an ideal of \(R\) defined as \(I(G)=(x_ix_j:\;\{x_i,x_j\}\) is an edge of \(G)\). In the paper under review, some bounds and descriptions for the Castelnuovo-Mumford regularity of the edge ideal of a graph \(G\) in terms of some combinatorial data from \(G\) are presented. Indeed, it is shown that \(\mathrm{reg}(R/I(G))\leq \mathrm{cochord}(G)\), where \(\mathrm{cochord}(G)\) denotes the minimum number of co-chordal subgraphs required to cover the edges of \(G\). Then for the families of weakly chordal graphs and well-covered bipartite graphs it was shown that \(\mathrm{indmatch}(G)=\mathrm{cochord}(G)\) and using this fact and considering the inequalities \(\mathrm{indmatch}(G)\leq \mathrm{reg}(R/I(G))\leq \mathrm{cochord}(G)\) (which holds for any graph \(G\)), it was shown that for these families of graphs one has \(\mathrm{reg}(R/I(G))=\mathrm{indmatch}(G)\), which recovers the result proved in [\textit{M. Kummini}, J. Algebr. Comb. 30, No. 4, 429-445 (2009; Zbl 1203.13018)] for the regularity of well-covered bipartite graphs. Moreover, using an special co-chordal cover it was shown that if \(V(G)\) can be partitioned into an independent set \(J_0\) together with \(s\) cliques \(J_1,\ldots,J_s\), then \(\mathrm{reg}(R/I(G))\leq s\). Also it was proved that if the subgraph of \(G\) induced on a subset \(J\) is a clique, then \(\mathrm{reg}(R/I(G))\leq \mathrm{reg}(R/I(G\setminus J))+1\). Also for an arbitrary graph \(G\), a lower bound for \(\mathrm{reg}(R/I(G))\) is given in terms of the induced subgraphs of \(G\) which are the disjoint union of edges and cycles.