Vertex decomposable graphs and obstructions to shellability
From MaRDI portal
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.
Recommendations
- Shellability, vertex decomposability, and lexicographical products of graphs
- Shellability of simple graphs and hypergraphs containing a simplicial vertex
- scientific article; zbMATH DE number 7660842
- Completing and extending shellings of vertex decomposable complexes
- Completing and extending shellings of vertex decomposable complexes
- scientific article; zbMATH DE number 5238175
- Vertex decomposability and regularity of very well-covered graphs
- A new construction for vertex decomposable graphs
- A new view toward vertex decomposable graphs
- scientific article; zbMATH DE number 3845624
Cites work
- Algebraic properties of edge ideals via combinatorial topology
- Cohen--Macaulay chordal graphs
- Cohen-Macaulay graphs
- Combinatorics and commutative algebra.
- Complexes of directed trees
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- Dirac-type characterizations of graphs without long chordless cycles
- Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property
- Domination numbers and homology
- Eigenvalues and homology of flag complexes and vector representations of graphs
- Graph Classes: A Survey
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 482758 (Why is no real title available?)
- scientific article; zbMATH DE number 1455118 (Why is no real title available?)
- scientific article; zbMATH DE number 1565322 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Obstructions to shellability
- On sequentially Cohen-Macaulay complexes and posets
- Poset topology: tools and applications
- Sequentially Cohen-Macaulay edge ideals
- Shellability of interval orders
- Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
- Shellable nonpure complexes and posets. II
- Simplicial simple-homotopy of flag complexes in terms of graphs
- Threshold graphs, shifted complexes, and graphical complexes
- Transitiv orientierbare Graphen
- Whiskers and sequentially Cohen-Macaulay graphs
Cited in
(98)- Sequentially Cohen-Macaulay bipartite graphs: Vertex decomposability and regularity
- Obstructions to shellability
- W₂-graphs and shedding vertices
- On vertex decomposable and Cohen-Macaulay regular graphs
- A characterization of shellable and sequentially Cohen-Macaulay hypercycles
- Graph operations preserving \(W_{2}\)-property
- Shedding vertices of vertex decomposable well-covered graphs
- On the powers of vertex cover ideals
- Upper bounds for the regularity of powers of edge ideals of graphs
- The v-number of edge ideals
- Well-covered and Cohen-Macaulay theta-ring graphs
- Shellability of polyhedral joins of simplicial complexes and its application to graph theory
- Cohen-Macaulay growing graphs
- Matching complexes of trees and applications of the matching tree algorithm
- Powers of componentwise linear ideals: the Herzog-Hibi-Ohsugi conjecture and related problems
- Rooted order on minimal generators of powers of some cover ideals
- A new view toward vertex decomposable graphs
- 1-well-covered graphs revisited
- A note on independence complexes of chordal graphs and dismantling
- Pure vertex decomposable simplicial complex associated to graphs whose 5-cycles are chorded
- Edge-stable equimatchable graphs
- Erdős-Ko-Rado theorems for simplicial complexes
- Vertex decomposability of 2-CM and Gorenstein simplicial complexes of codimension 3
- Componentwise linearity of powers of cover ideals
- Expansion of a simplicial complex
- On well-covered, vertex decomposable and Cohen-Macaulay graphs
- Shellability of simple graphs and hypergraphs containing a simplicial vertex
- Sequentially S_r simplicial complexes and sequentially S₂ graphs
- Two lower bounds for the Stanley depth of monomial ideals
- A new construction for Cohen-Macaulay graphs
- Balanced vertex decomposable simplicial complexes and their \(h\)-vectors
- Results on the regularity of square-free monomial ideals
- Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity
- Splittings of independence complexes and the powers of cycles
- Squarefree zero-divisor graphs of Stanley-Reisner rings
- Complement of special chordal graphs and vertex decomposability
- Shellability, vertex decomposability, and lexicographical products of graphs
- k-shellable simplicial complexes and graphs
- Regularity and projective dimension of edge ideals
- Algebraic study on Cameron-Walker graphs
- Shellability of the higher pinched Veronese posets
- Simplicial complexes satisfying Serre's condition: a survey with some new results
- Symbolic powers of cover ideals of graphs and Koszul property
- A class of well-covered and vertex decomposable graphs arising from rings
- Symbolic powers of vertex cover ideals
- Higher independence complexes of graphs and their homotopy types
- Topology of clique complexes of line graphs
- Stanley-Reisner rings
- On graphs admitting two disjoint maximum independent sets
- Vertex decomposability of complexes associated to forests
- Geometric vertex decomposition and liaison
- Very well-covered graphs and their h-vectors
- A note on Cohen-Macaulay skeletons of cycles and vertex-decomposability
- Cohen-Macaulay graphs with large girth
- On the sequentially Cohen-Macaulay properties of almost complete multipartite graphs
- Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness
- Boolean graphs are Cohen–Macaulay
- Some algebraic properties of \(t\)-clique ideals
- Regularity and projective dimension of the edge ideal of C₅-free vertex decomposable graphs
- scientific article; zbMATH DE number 5264897 (Why is no real title available?)
- The Edge Ideals of Complete Multipartite Hypergraphs
- Bouquets, vertex covers and edge ideals
- Independence complexes of well-covered circulant graphs
- Upper bounds for the regularity of symbolic powers of certain classes of edge ideals
- scientific article; zbMATH DE number 7660842 (Why is no real title available?)
- Dominating induced matchings of finite graphs and regularity of edge ideals
- Line graphs with a Cohen-Macaulay or Gorenstein clique complex
- Shedding vertices and ass-decomposable monomial ideals
- Chordal graphs, higher independence and vertex decomposable complexes
- Gorenstein and Cohen–Macaulay matching complexes
- Regularity of edge ideals of \(C_{4}\)-free graphs via the topology of the lcm-lattice
- The regularity of almost all edge ideals
- Critical equimatchable graphs
- Vertex decomposability and regularity of very well-covered graphs
- Chordal and sequentially Cohen-Macaulay clutters
- Graphs with all holes the same length
- Recognizing \(\text{W}_2\) graphs
- Vertex decomposability, shellability and Cohen-Macaulayness of graphs upon graph operations
- The sequentially Cohen-Macaulay property of edge ideals of edge-weighted graphs
- The weak Lefschetz property of whiskered graphs
- Three invariants of geometrically vertex decomposable ideals
- Extending simplicial complexes: topological and combinatorial properties
- 1-well-covered graphs containing a clique of size \(n/3\)
- A remark on sequentially Cohen-Macaulay monomial ideals
- Prime graphs, matchings and the Castelnuovo-Mumford regularity
- Complexity of simplicial homology and independence complexes of chordal graphs
- The Stanley-Reisner ideal of the rook complex of polyominoes
- Unmixed and sequentially Cohen-Macaulay skew tableau ideals
- Recognizing relating edges in graphs without cycles of length 6
- Cohen-Macaulay edge-weighted graphs of girth 5 or greater
- Down-left graphs and a connection to toric ideals of graphs
- Strict Erdős-Ko-Rado for simplicial complexes (extended abstract)
- Cohen-Macaulay oriented graphs with large girth
- On the homotopy type of the polyhedral join over the independence complex of a forest
- Vertex decomposability criteria for path ideal complexes
- On the classification of planar-rips complexes and their corresponding unit disk graphs
- Partial coloring, vertex decomposability and sequentially Cohen-Macaulay simplicial complexes
- Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
This page was built for publication: Vertex decomposable graphs and obstructions to shellability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182562)
