1 registro encontrado - programa Programa de Pós-Graduação em Ciência da Computação E área de concentração Matemática Discreta e Combinatória
Grafos pfaffianos e problemas relacionados
Miranda, Alberto Alexandre Assis
TESE - Português
Número de chamada: T/UNICAMP M672g
Publicação: Campinas, SP : [s.n.], 2009.
Assunto: Teoria dos grafos
Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro...
Ver mais
Resumo
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
BCCL (1)
IMECC (1)
IMECC (1)