A Characterization of Parity Graphs Containing no Cycle of Order Five or Less

The class of parity graphs, those in which the cardinality of every maximal independent subset of vertices has the same parity, contains the well-covered graphs and arose in connection with the PSPACE-complete game “Generalized Kayles”. In 1983 [5] we characterized parity graphs of girth 8 or more. This is extended to a characterization of the parity graphs of girth greater than 5. We deduce that these graphs can be recognized in polynomial time.