Abstract
This project's goal is to define some Pfaffian graphs related problems complexity class (P, NP, co-NP, NP-complete, etc). Pfaffian graphs are the graph whose edges can be oriented such that each conformal circuit with an even number of vertices has an odd orientation. No characterization is known for any Pfaffian graphs. It is not even known whether the problem of determining if a given g…