A characterisation of Pfaffian near bipartite graphs (Q1850543)

If \(v\) and \(w\) are vertices in a directed graph, then we denote by \((v,w)\) an edge directed from \(v\) to \(w\). Now let \(G^*\) be a directed graph with an even number \(2n\) of vertices and let \(F\) be the set \(\{f_1,f_2,\dots, f_k\}\) of 1-factors of \(G^*\). For all \(i\) write \[ f_i= \{(u_{i1}, w_{i1}), (u_{i2}, w_{i2}),\dots, (u_{in}, w_{in})\}, \] where \(u_{ij}\) and \(w_{ij}\) are vertices of \(G^*\) for each \(j\). Associate with \(f_i\) a plus sign if \[ u_{i1} w_{i1} u_{i2} w_{i2}\cdots u_{in} w_{in} \] is an even permutation of \[ u_{11} w_{11} u_{12} w_{12}\cdots u_{1n} w_{1n}, \] and a minus sign otherwise. An undirected graph is said to be Pfaffian if it has an orientation under which all the 1-factors have the same sign. Pfaffian orientations have been used by \textit{P. W. Kasteleyn} [Graph Theory Theor. Phys., 43-110 (1967; Zbl 0205.28402)] to enumerate 1-factors in a graph. A graph is 1-extendible if every edge has a 1-factor containing it. A 1-extendible non-bipartite graph \(G\) is said to be near bipartite if there exists \(e_1\) and \(e_2\) such that \(G- \{e_1,e_2\}\) is 1-extendible and bipartite. We characterise the Pfaffian near bipartite graphs in terms of forbidden subgraphs. The theorem extends an earlier characterisation of Pfaffian bipartite graphs.