Towards a characterisation of Pfaffian near bipartite graphs (Q1349098): Difference between revisions

Let \(G\) be a finite, simple graph (directed or undirected), the vertex set of \(G\) is denoted by \(V(G)\) and the edge set by \(E(G)\). It is known that a 1-factor of \(G\) is a subset \(f\) of \(E(G)\) such that every vertex has a unique edge of \(f\) incident to it and a graph is 1-extendible if every edge has a 1-factor containing it. Further, an ear is a path of odd cardinality and every 1-extendible graph \(G\) has an ear decomposition \(K_2= G_0,G_1,\dots, G_t= G\) such that the 1-extendible graph \(G_i\) is obtained from the 1-extendible graph \(G_{i-1}\) by the adjunction of one or two ears. This is the content of the 2-ear theorem of Lovász and Plummer. By introducing the concept of an even subdivision \(H\) of a graph \(G\), a Pfaffian bipartite graph \(G^*\) can be characterized in the following manner: A bipartite graph \(G^*\) is Pfaffian iff it does not contain an even subdivision \(H\) of \(K_{3,3}\) such that \(G^*-V(H)\) contains a 1-factor. In the present paper, the authors show that the investigation of these Pfaffian graphs can be restricted to 1-extendible graphs which have an ear decomposition with a unique 2-ear adjunction. By this result the investigation of Pfaffian graphs with an ear decomposition was suggested where the unique 2-ear adjunction is the final adjunction: \(G_t\) is obtained from \(G_{t-1}\) by the adjunction of two ears. Such graphs are called ``near bipartite''. Here, the authors get the result that for a 1-extendible graph \(G\) that can be obtained from a 1-extendible bipartite graph \(K\) by a 2-ear adjunction and with some further assumptions the following holds: A graph \(G\) is non-Pfaffian iff it has a subgraph \(H\), reducible to an even subdivision of \(K_{3,3}\), such that \(G-V(H)\) has a 1-factor. The continuation of these investigations is already announced by the references.