The complement of a connected bipartite graph is vertex decomposable

Abstract

Associated to a simple undirected graph $G$ is a simplicial complex ${\Delta }_G$ whose faces correspond to the independent sets of $G$. A graph $G$ is called vertex decomposable if ${\Delta }_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 $\overline{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 ${\Delta }_{\overline{G}}$.

5 pages