The complement of a connected bipartite graph is vertex decomposable

2009/02/25 by Mohammad Mahmoudi, Mahmoudi, Mohammad, Amir Mousivand +3
Computer Science · Mathematics · #05C75 #13H10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.0902.4342

openalex publication_date 2009/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Associated to a simple undirected graph G is a simplicial complex Δ_G whose faces correspond to the independent sets of G. A graph G is called vertex decomposable if Δ_G is a vertex decomposable simplicial complex. We are interested in determining what families of graph have the property that the complement of G, denoted by G, is vertex decomposable. We obtain the result that the complement of a connected bipartite graph is vertex decomposable and so it is Cohen-Macaulay due to pureness of Δ_G.

Related

• Shedding vertices of vertex decomposable graphs
• Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity
• Chordal graphs, higher independence and vertex decomposable complexes
• On vertex decomposability and regularity of graphs
• Total Cut Complexes of Graphs