A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs

A matching covered graph is a nontrivial connected graph in which every edge is in some perfect matching. A matching covered graph G is near-bipartite if it is non-bipartite and there is a removable double ear R such that G-R is matching covered and bipartite. In 2000, C. Little and I. Fischer characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs. However, their characterization does not imply a polynomial time algorithm to determine whether a near-bipartite graph is Pfaffian. In this report, we give such an algorithm. Our algorithm is based in a Inclusion-Exclusion principle and uses as a subroutine an algorithm by McCuaig and by Robertson, Seymour and Thomas that determines whether a bipartite graph is Pfaffian.

2007