Parity graph

[1] This class of graphs was named and first studied by Burlet & Uhry (1984).

For, in a parity graph, any long odd cycle can be partitioned into two paths of different parities, neither of which is a single edge, and at least one chord is needed to prevent these from both being induced paths.

Then, partitioning the cycle into two paths between the endpoints of this first chord, a second chord is needed to prevent the two paths of this second partition from being induced.

[1] They are exactly the graphs whose Cartesian product with a single edge remains perfect.

For instance, using the split decomposition, it is possible to find the weighted maximum independent set of a parity graph in polynomial time.

A parity graph (the unique smallest cubic , matchstick graph ) that is neither distance-hereditary nor bipartite