Abstract | ||
---|---|---|
Associated to a simple undirected graph G is a simplicial complex @D"G whose faces correspond to the independent sets of G. We call a graph G shellable if @D"G is a shellable simplicial complex in the non-pure sense of Bjorner-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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.jcta.2007.11.001 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
edge ideals,sequentially cohen-macaulay,simplicial complex,sequentially cohen–macaulay,totally balanced clutter.,simple undirected graph,shellable graph,totally balanced clutter,. shellable complex,shellable simplicial complex,shellable complex,bipartite and chordal graphs,shellable bipartite graph,bipartite graph,sequentially cohen-macaulayness,graph g shellable,sequentially cohen-macaulay bipartite graph,chordal graph,independent set | Discrete mathematics,Complete bipartite graph,Graph,Indifference graph,Combinatorics,Chordal graph,Bipartite graph,Simplicial complex,Pathwidth,Mathematics,Recursion | Journal |
Volume | Issue | ISSN |
115 | 5 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
13 | 1.04 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Adam Van Tuyl | 1 | 15 | 4.32 |
Rafael H. Villarreal | 2 | 75 | 15.69 |