@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.
  }
}