Shellable graphs and sequentially Cohen–Macaulay bipartite graphs

AbstractAssociated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner–Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen–Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley–Reisner ring is sequentially Cohen–Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen–Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen–Macaulayness of simplicial forests