Towards a characterisation of Pfaffian graphs

1999/09/03 by Charles H. C. Little, Little, Charles H. C., Franz Rendl +3
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C70

paper · pdf · doi:10.48550/arxiv.math/9909026

added references

openalex publication_date 1999/09/03 · arxiv created 1999/09/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A bipartite graph G is known to be Pfaffian if and only if it does not contain an even subdivision H of K_3,3 such that G - VH contains a 1-factor. However a general characterisation of Pfaffian graphs in terms of forbidden subgraphs is currently not known. In this paper we describe a possible approach to the derivation of such a characterisation. We also extend the characterisation for bipartite graphs to a slightly more general class of graphs.

Related

• A characterisation of Pfaffian near bipartite graphs
• Even Orientations and Pfaffian graphs
• Face-width of Pfaffian Braces and Polyhex Graphs on Surfaces
• Replacing Pfaffians and applications
• Computing the permanental polynomials of bipartite graphs by Pfaffian orientation