Orientações Pfaffian de Grafos e Aplicações

O assunto tratado neste projeto de pesquisa insere-se na subárea da teoria da computação denominada teoria dos grafos. O problema que é objeto de pesquisa deste projeto pode ser descrito da seguinte forma: Dado um grafo simples G e um emparelhamento  perfeito M de G, queremos orientar as arestas de G de tal forma que todos os circuitos M-alternados tenham paridade ímpar, ou seja, ao percorrermos um tal circuito em algum sentido encontramos um número ímpar de arestas orientadas nesse sentido. Nem todo  grafo admite uma orientação com esta propriedade, por exemplo, K3,3 e o grafo de Petersen não admitem uma tal orientação. O problema da orientação Pfaffian consiste em decidir se um dado grafo admite uma orientação que satisfaz a propriedade acima. Este problema está relacionado com alguns problemas fundamentais em teoria dos grafos, como o problema da contagem de emparelhamentos perfeitos e o de decidir se um grafo orientado possui circuito orientado com um número par de arestas. Até o momento, o problema  da orientação Pfaffian foi resolvido apenas para algumas classes de grafos: Grafos planares, grafos bipartidos, grafos quase-bipartidos e grafos sólidos. Neste projeto, pretendemos explorar e determinar novas condições necessárias e suficientes  para que um grafo admita uma orientação Pfaffian visando resolver o problema para classes mais gerais de grafos.

Coordenador: Marcelo Henriques de Carvalho