Defesa de Tese de Doutorado: Diego Zuquim Guimarães Garcia
Document Actions
Defesa de Tese de Doutorado: Alberto Alexandre Assis Miranda
GRAFOS PFAFFIANOS E PROBLEMAS RELACIONADOS.
| What | Defesa de Doutorado |
|---|---|
| When |
26/10/2009 from 10:30 to 14:30 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
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 é um contra-exemplo para a
conjectura de Norine de que o número Pfaffiano de todo grafo é uma
potência de quatro. Na verdade, apresentamos um grafo cujo número
Pfaffiano é $6$. Junto com este contra-exemplo, apresentamos teoremas
que explicam um pouco melhor as propriedades de grafos $4$-Pfaffianos,
e um método para a geração de exemplos de grafos $2r$-Pfaffianos.
Concurso Público para Professor Doutor - MS-3
