Pfaffian Orientations and the Elusive Heawood Graph
Abstract
This paper describes the work presented in the master dissertation “Orientações Pfafanas e o Furtivo Grafo de Heawood”, available at “http://www.ic.unicamp.br/~miranda/dissertacao.pdf”, whose defense took place in August 7th, 2006, at the Institute of Computing, Unicamp. The use of Pfafans in matching theory is due to Tutte [Tutte 1998]. While it was not possible to nd a formula for the number of perfect matchings of a graph, Tutte used Pfafans to prove his famous characterization of graphs that have a perfect matching. In 1975, C. Little presented a characterization of bipartite Pfafan graphs. But it was only in 1998 that McCuaig and, independently, Robertson, Seymour and Thomas proved a theorem that implies a polynomial time algorithm to determine whether a bipartite graph is Pfafan. Our dissertation presented a new proof of that theorem.
References
Hopcroft, J. and Tarjan, R. (1974). Efficient planarity testing. J. ACM, 21(4):549–568.
Kasteleyn, P. W. (1963). Dimer statistics and phase transitions. J. Math. Phys., 4:287–293.
Little, C. and Rendl, F. (1991). Operations preserving the Pfaffian property of a graph. Austral Math. Soc., Series A(50):248–257.
Little, C. H. C. (1975). A characterization of convertible (0, 1)-matrices. J. Combin. Theory Ser. B, 18:187–208.
Little, C. H. C. and Fischer, I. (2001). A characterisation of Pfaffian near bipartite graphs. J. Combin. Theory Ser. B, 82:175–222.
Lovász, L. and Plummer, M. D. (1986). Matching Theory. Number 29 in Annals of Discrete Mathematics. Elsevier Science.
McCuaig, W. (2001). Brace generation. J. Graph Theory, 38:124–169.
McCuaig, W. (2004). Pólya’s permanent problem. The Electronic J. of Combin., 11.
Robertson, N., Seymour, P. D., and Thomas, R. (1999). Permanents, Pfaffian orientations and even directed circuits. Ann. of Math. (2), 150:929–975.
Tutte, W. T. (1998). Graph Theory as I Have Known It. Number 11 in Oxford Lecture Series in Mathematics and its Applications. Clarendon Press, Oxford.
