Bolsa 02/05665-6 - Teoria dos grafos - BV FAPESP
Busca avançada
Ano de início
Entree

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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.

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.