Matching Signatures and Pfaffian Graphs

We prove that every 4-Pfaffian that is not Pfaffian essentially has a unique signature matrix. We also give a simple composition Theorem of $2r$-Pfaffian graphs from $r$ Pfaffian spanning subgraphs. We apply these results and exhibit a graph that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine, which states that if a graph $G$ is $k$-Pfaffian but not $(k-1)$-Pfaffian then $k$ is a power of four.

2009