Towards a characterisation of Pfaffian near bipartite graphs

A bipartite graph <f>G</f> is known to be Pfaffian if and only if it does not contain an even subdivision <f>H</f> of <f>K3,3</f> such that <f>G−VH</f> 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 Lova´sz and Plummer is likely to play a crucial roˆle in such a characterisation. The theorem asserts that every 1-extendible graph <f>G</f> has an ear decomposition <f>K2=G0,G1,…,Gt=G</f> such that the 1-extendible graph <f>Gi</f> is obtained from the 1-extendible graph <f>Gi−1</f> 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., <f>Gt</f> is obtained from <f>Gt−1</f> by the adjunction of two ears. Such graphs are called ‘near bipartite’. [Copyright &y& Elsevier]