2000/02/09 by Ilse Fischer, Fischer, Ilse, C. H. C. Little +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0002062
arxiv created 2000/02/09 · openalex publication_date 2000/02/09 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1967 Kasteleyn introduced a powerful method for enumerating the 1-factors of planar graphs. In fact his method can be extended to graphs which permit an orientation under which every alternating circuit is clockwise odd. Graphs with this property are called \it Pfaffian. Little characterised Pfaffian bipartite graphs in terms of forbidden subgraphs in 1975. We extend his characterisation to near bipartite graphs.