Pfaffian graphs and related problems

Author(s)

Alberto Alexandre Assis Miranda

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2009-10-26

Examining board members

Cláudio Leonardo Lucchesi; U.S.R Murty; Jayme Luiz Szwarcfiter; Yoshiko Wakabayashi; Orlando Lee

• Advisor: Cláudio Leonardo Lucchesi

Abstract

The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 (AU)

• FAPESP's process: 05/04426-6 - Pfaffian graphs and related problems
• Grantee: Alberto Alexandre Assis Miranda
• Support Opportunities: Scholarships in Brazil - Doctorate