Recognizing near-bipartite Pfaffian graphs in polynomial time

DOI10.1016/J.DAM.2009.01.008zbMATH Open1228.05234OpenAlexW2000008285MaRDI QIDQ987672FDOQ987672

Authors: Alberto Alexandre Assis Miranda, Cláudio L. 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

Recommendations

• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• Minimally non-Pfaffian graphs
• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• A characterisation of Pfaffian near bipartite graphs
• Matching signatures and Pfaffian graphs

zbMATH Keywords

perfect matchingmatching covered graphsPfaffian graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• A characterisation of Pfaffian near bipartite graphs
• Minimally non-Pfaffian graphs
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• A note on cyclic connectivity and matching properties of regular graphs
• Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles
• Towards a characterisation of Pfaffian near bipartite graphs
• Recognizing generalized Petersen graphs in linear time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987672)