Orientações Pfafanas e o Furtivo Grafo de Heawood
Resumo
Este artigo descreve o trabalho feito na dissertação de mestrado “Orientações Pfafanas e o Furtivo Grafo de Heawood”, disponível no endereço “http://www.ic.unicamp.br/~miranda/dissertacao.pdf”, defendida no dia 7 de agosto de 2006, no Instituto de Computação da Unicamp. A idéia de usar Pfafanos em teoria dos emparelhamentos é devida a Tutte [Tutte 1998]. Apesar de não ter encontrado uma fórmula para o número de emparelhamentos perfeitos de um grafo como desejava, Tutte usou Pfafanos para provar sua famosa caracterização de grafos que têm emparelhamento perfeito. Em 1975, Little apresentou uma caracterização de grafos bipartidos Pfafanos. Mas foi somente em 1998 que McCuaig e, independentemente, Robertson, Seymour e Thomas provaram um teorema que implica em um algoritmo de tempo polinomial que determina se um grafo bipartido é Pfafano. Nossa dissertação apresentou uma nova demonstração para esse teorema.
Referências
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.
