Vertex decomposable graphs and obstructions to shellability

Abstract

Inspired by several recent papers on the edge ideal of a graph G, we study the equivalent notion of the independence complex of G. Using the tool of vertex decomposability from geometric combinatorics, we show that 5-chordal graphs with no chordless 4-cycles are shellable and sequentially Cohen-Macaulay. We use this result to characterize the obstructions to shellability in flag complexes, extending work of Billera, Myers, and Wachs. We also show how vertex decomposability may be used to show that certain graph constructions preserve shellability.

13 pages, 3 figures. v2: Improved exposition, added Section 5.2 and additional references. v3: minor corrections for publication

References in corpus (1)

• Simplicial simple-homotopy of flag complexes in terms of graphs

Cited by in corpus (48)

• Edge ideals: algebraic and combinatorial properties
• Boij-Söderberg theory: Introduction and survey
• Results on the regularity of square-free monomial ideals
• Cohen-Macaulay graphs and face vectors of flag complexes
• Erdos-Ko-Rado theorems for simplicial complexes
• Upper bounds for the regularity of powers of edge ideals of graphs
• Geometric vertex decomposition and liaison
• On Generalizations of Cycles and Chordality to Hypergraphs from an Algebraic Viewpoint
• Vertex decomposable graphs, codismantlability, Cohen-Macaulayness and Castelnuovo-Mumford regularity
• Boolean graphs are unmixed and vertex decomposable
• Second powers of cover ideals of paths
• Chordal graphs, higher independence and vertex decomposable complexes
• Higher Independence Complexes of graphs and their homotopy types
• Topology of Clique Complexes of Line Graphs
• Symbolic powers of vertex cover ideals
• Projective Dimension, Graph Domination Parameters, and Independence Complex Homology
• Graphs with all holes the same length
• Gorenstein and Cohen-Macaulay Matching Complexes
• Shedding vertices of vertex decomposable graphs
• Regularity via topology of the lcm-lattice for $C_4$-free graphs
• Algebraic study on Cameron-Walker graphs
• On shellability for a poset of even subgraphs of a graph
• Symbolic Powers of Cover Ideals of Graphs and Koszul Property
• Sequentially $S_r$ simplicial complexes and sequentially $S_2$ graphs
• Cohen-Macaulay graphs with large girth
• Three invariants of geometrically vertex decomposable ideals
• Herzog, Hibi and Ohsugi conjecture for trees
• Independence complexes of hypergraphs and bounded degree complexes
• Algebraic Properties of Clique Complexes of Line Graphs
• Dominating induced matchings of finite graphs and regularity of edge ideals
• Bouquets, vertex covers and edge ideals
• 1-well-covered graphs revisited
• Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity
• Face Numbers of Certain Cohen-Macaulay Flag Complexes
• A new construction for Cohen-Macaulay graphs
• The complement of a connected bipartite graph is vertex decomposable
• Regularity and projective dimension of edge ideal of $C_5$-free vertex decomposable graphs
• Rooted order on minimal generators of powers of some cover ideals
• Partial coloring, vertex decomposability, and sequentially Cohen-Macaulay simplicial complexes
• Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness
• Down-left graphs and a connection to toric ideals of graphs
• Componentwise Linearity of Powers of Cover Ideals
• Shellability of complexes of directed trees
• Vertex decomposability of complexes associated to forests
• Shedding vertices and Ass-decomposable monomial ideals
• Cohen Macaulay Hybrid Graphs
• Splittings of independence complexes and the powers of cycles
• The edge ideals of complete multipartite hypergraphs