Minimally non-Pfaffian graphs

DOI10.1016/j.jctb.2007.12.005zbMath1171.05040OpenAlexW2051271137MaRDI QIDQ947729

Serguei Norine, Robin Thomas

Publication date: 7 October 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2007.12.005

zbMATH Keywords

graphPfaffian orientationperfect matchingfactor-critical graphPfaffian factor critical graphspolynomial time recognition algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Dimers on the \(3^3 . 4^2\) lattice ⋮ A conjecture of Norine and Thomas for abelian Cayley graphs ⋮ A generalization of Little's theorem on Pfaffian orientations ⋮ The Pfaffian property of Cayley graphs on dihedral groups ⋮ Pfaffian orientations for a type of bipartite graph ⋮ Enumeration of perfect matchings of the Cartesian products of graphs ⋮ The Pfaffian property of circulant graphs ⋮ The Pfaffian property of Cartesian products of graphs ⋮ On essentially 4-edge-connected cubic bricks

Cites Work

• Unnamed Item
• Unnamed Item
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pfaffian labelings and signs of edge colorings
• Brick decompositions and the matching rank of graphs
• Matching theory
• Matching structure and the matching lattice
• Towards a characterisation of Pfaffian near bipartite graphs
• Pólya's permanent problem
• A characterization of convertible (0,1)-matrices
• A characterisation of Pfaffian near bipartite graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Generating bricks
• The statistics of dimers on a lattice
• Statistical Mechanics of Dimers on a Plane Lattice

This page was built for publication: Minimally non-Pfaffian graphs