@techreport{TR-IC-07-15,
number = {IC-07-15},
author = {Alberto Alexandre Assis Miranda and
Cl\'audio Leonardo Lucchesi},
title = {A Polynomial Time Algorithm for Recognizing
Near-Bipartite {Pfaffian} Graphs},
month = {May},
year = {2007},
institution = {Institute of Computing, University of Campinas},
note = {In English, 6 pages.
\par\selectlanguage{english}\textbf{Abstract}
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.
}
}