On Planar Quasi-Parity Graphs
Cláudia Linhares Sales, Frédéric Maffray, Bruce A. Reed · SIAM Journal on Discrete Mathematics · 2008
A graph G is strict quasi parity (SQP) if every induced subgraph of G that is not a clique contains a pair of vertices with no odd chordless path between them (an even pair). Hougardy conjectured that the minimal forbidden subgraphs for the class of SQP graphs are the odd chordless cycles, the complements of odd or even chordless cycles, and some line-graphs of bipartite graphs. Here we prove this conjecture for planar graphs. We also give a constructive characterization of all the planar minimal forbidden subgraphs for the class of SQP graphs.