A characterisation of Pfaffian near bipartite graphs

Authors
Fischer, I
Citation
I. Fischer, A characterisation of Pfaffian near bipartite graphs, J COMB TH B, 82(2), 2001, pp. 175-222
Citations number
7
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
82
Issue
2
Year of publication
2001
Pages
175 - 222
Database
ISI
SICI code
0095-8956(200107)82:2<175:ACOPNB>2.0.ZU;2-1
Abstract
A graph is 1-extendible if every edge has a 1-factor containing it. A 1-ext endible non-bipartite graph G is said to be near bipartite if there exist e dges e(1) and e(2) such that G - { e(1), e(2)} is 1-extendible and bipartit e. We characterise the Pfaffian near bipartite graphs in terms of forbidden subgraphs. The theorem extends an earlier character isa lion of Pfaffian b ipartite graphs. (C) 2001 Academic Press.