Almost Parity Graphs and Claw-Free Parity Graphs

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, \(\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, \(\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.