Recognizing near-bipartite Pfaffian graphs in polynomial time |
| |
Authors: | Alberto Alexandre Assis Miranda Cláudio Leonardo Lucchesi |
| |
Institution: | Institute of Computing, University of Campinas, Caixa Postal 6176, 13083-852 Campinas, SP, Brazil |
| |
Abstract: | A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e1 and e2 such that G−e1−e2 is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class. |
| |
Keywords: | Pfaffian Matching covered graphs Perfect matching |
本文献已被 ScienceDirect 等数据库收录! |
|