Recognizing near-bipartite Pfaffian graphs in polynomial time

DOI10.1016/j.dam.2009.01.008zbMath1228.05234OpenAlexW2000008285MaRDI QIDQ987672

Alberto Alexandre Assis Miranda, Cláudio Leonardo Lucchesi

Publication date: 13 August 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.01.008

zbMATH Keywords

perfect matchingmatching covered graphsPfaffian graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

A note on cyclic connectivity and matching properties of regular graphs

Cites Work

• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Matching theory
• Pólya's permanent problem
• A characterisation of Pfaffian near bipartite graphs
• Permanents, Pfaffian orientations, and even directed circuits
• On the number of dissimilar pfaffian orientations of graphs

This page was built for publication: Recognizing near-bipartite Pfaffian graphs in polynomial time