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 | |
TITULO | |
Matéria(s) publicada(s) em Outras Mídias ( ): | |
Mais itensMenos itens | |
VEICULO: TITULO (DATA) | |
VEICULO: TITULO (DATA) | |