O problema da orientação pfaffiana de grafos

Abstract

Um circuito C em um grafo G é alternado se existe um emparelhamento perfeito M de G tal que C é M-alternado. Uma orientação das arestas de um grafo G é uma orientação pfaffiana se, ao percorrermos qualquer circuito alternado em algum sentido, encontramos um número ímpar de arestas orientadas neste mesmo sentido, ou seja, todos os circuitos alternados do grafo possuem paridade ímpar. Se um grafo possui uma orientação pfaffiana, então dizemos que ele é pfaffiano. Nem todo grafo é pfaffiano, como por exemplo o grafo de Petersen e o K3;3. Por isso, decidir se um dado grafo possui, ou não, uma orientação pfaffiana é um problema de grande importância, pois, além de estar relacionado com alguns problemas fundamentais na teoria dos grafos, como determinar o número de emparelhamentos perfeitos em um grafo1, são foi resolvido para algumas classes de grafos: grafos planares, grafos bipartidos, grafos quase-bipartidos e grafos sólidos. Neste trabalho, estudaremos a caracterização do problema da orientação pfaffiana de grafos paras as classes de grafos bipartidos e planares. Além disso, estudaremos parte da teoria de grafos cobertos por emparelhamentos para apresentar uma nova demostração de uma caracterização de grafos pfaffianos dada por Lovász e Plummer em [9].

A circuit C in a graph G is alternating if there is a perfect matching M of G such that C is M-alternating. An orientation of the edges of a graph G is Pfaffian if, regardless of the sense of transversal of any alternating circuit, the number of forward edges is odd. In other words, every alternating circuit of G is oddly oriented. If a graph G admits a Pfaffian orientation, then we say that G is Pfaffian. But not every graph is Pfaffian, as well as Petersen graph and K3;3. That's why deciding if a given graph has, or not, a Pfaffian orientation is a relevant problem related to some fundamental problems in graphs theory, like to determine the number of perfect matching in a graph2, and it was solved for only four classes of graphs: planar graphs, bipartite graphs, near-bipartite graphs and solid graphs. In this work, we study caracterizations to the pfaffian orientation problem for bipartite and planar graphs, as well as part of matching covered graphs theory, which one we use to present a new proof of a caracterization of Pfaffian graphs due to Lovasz and Plummer in [9].