Conjeturas de tutte e emparelhamentos em grafos bipartidos.

• Processo: 02/05665-6
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de março de 2003
• Data de Término da vigência: 28 de fevereiro de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cláudio Leonardo Lucchesi
• Beneficiário: Candida Nunes da Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Conjeturas De Tutte | Fluxos Inteiros | Grafos Bipartidos | Teoria Dos Grafos

Resumo

O tema central do trabalho é fluxos inteiros em grafos, mais especificamente as conjeturas de Tutte sobre k-fluxos. Ao longo das décadas de 50, 60 e 70, Tutte propôs três conjeturas bastante conhecidas sobre k-fluxos inteiros em grafos não orientados. Estas são as Conjeturas dos 5-, 4- e 3-Fluxos. Sabemos que as Conjeturas dos 5- e 3-Fluxos podem ser reduzidas para as subclasses dos grafos cúbicos e 5- regulares, respectivamente. Minha dissertação de mestrado apresenta uma caracterização dos grafos que admitem um 3-fluxo como aqueles que possuem uma eqüipartição com certas propriedades especiais, a qual denominamos eqüipartição mod 3-orientavel. Além disso, a dissertação apresenta duas caracterizações de eqüipartições mod 3-orientáveis em termos (i) da existência de um emparelhamento perfeito em um grafo bipartido derivado da eqüipartição e (ii) do tamanho dos cortes de arestas do grafo. No doutorado pretendemos estender os resultados do mestrado de duas formas principais: (i) pesquisando se também é possível caracterizar os grafos cúbicos que admitem 5-fluxo pela existência de uma eqüipartição com propriedades especiais e (ii) pesquisando se é possível definir subclasses de grafos 5-regulares que sempre possuem uma eqüipartição mod 3-orientável. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SILVA, Candida Nunes da. Fluxos inteiros e colorações. 2009. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.