An Odd Pfaffian Number
In the authors' words
The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.