Almost Parity Graphs and Claw-Free Parity Graphs

Abstract

A graph $G$ is well-covered if every maximum independent set of vertices of $G$ has the same cardinality. A graph $G_1$ is an almost well-covered graph if it is not well-covered, but $G_1\setminus \{v\}$ is well-covered, $\mathrm{\forall }v\in V(G_1)$. Similarly, a graph $H$ is a parity graph if every maximal independent set of vertices of $H$ has the same parity, and a graph $H_1$ is an almost parity graph if $H_1$ is not a parity graph but $H_1\setminus \{h\}$ is a parity graph, $\mathrm{\forall }h\in V(H_1)$. Here, we will give a complete characterization of almost parity graphs. We also prove that claw-free parity graphs must be well-covered.