Grafos pfaffianos e problemas relacionados

Autor(es)

Alberto Alexandre Assis Miranda

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2009-10-26

Membros da banca

Cláudio Leonardo Lucchesi; U.S.R Murty; Jayme Luiz Szwarcfiter; Yoshiko Wakabayashi; Orlando Lee

• Orientador: Cláudio Leonardo Lucchesi

Resumo

A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 (AU)

• Processo FAPESP: 05/04426-6 - Grafos pfaffianos e problemas relacionados
• Beneficiário: Alberto Alexandre Assis Miranda
• Modalidade de apoio: Bolsas no Brasil - Doutorado