Towards a characterisation of Pfaffian near bipartite graphs Original Research Article

A bipartite graph G is known to be Pfaffian if and only if it does not contain an even subdivision H of K3,3 such that G−VH contains a 1-factor. However a general characterisation of Pfaffian graphs in terms of forbidden subgraphs is currently not known. The 2-ear theorem of Lovász and Plummer is likely to play a crucial rôle in such a characterisation. The theorem asserts that every 1-extendible graph G has an ear decomposition K2=G0,G1,…,Gt=G such that the 1-extendible graph Gi is obtained from the 1-extendible graph Gi−1 by the adjunction of one or two ears. In this paper we first show that we can restrict the study of Pfaffian graphs to 1-extendible graphs which have an ear decomposition with a unique 2-ear adjunction. Motivated by that result we start a characterisation of Pfaffian graphs with an ear decomposition where the unique 2-ear adjunction is the final adjunction, i.e., Gt is obtained from Gt−1 by the adjunction of two ears. Such graphs are called ‘near bipartite’