03 set 2021
14:00 Defesa de Mestrado Integralmente a distância
Tema
A conjetura dos 3-fluxos de Tutte para grafos quase pares
Aluno
Léo Vieira Peres
Orientador / Docente
Ricardo Dahab
Breve resumo
Um grafo G admite um 3-fluxo se existe uma orientação de G e uma atribuição de pesos em {1, 2} às arestas de G tal que, para todo vértice v do grafo, a soma dos pesos das arestas entrando em v é igual à soma do peso das arestas saindo de v. A conjetura dos 3-fluxos de Tutte afirma que todo grafo 4-aresta-conexo admite um 3-fluxo. Uma versão equivalente dessa conjetura é perguntar se todo grafo 2-aresta-conexo com no máximo três cortes de aresta de tamanho três admite um 3-fluxo. Nosso objetivo é caracterizar quais grafos com até quatro cortes de aresta de tamanho três admitem um 3-fluxo, para algumas classes restritas de grafos. Nós focamos em grafos com até seis vértices de grau ímpar. Nós provamos uma caracterização completa para grafos com até quatro vértices de grau ímpar e uma caracterização parcial para grafos com seis vértices de grau ímpar.
Banca examinadora
Titulares:
| Ricardo Dahab | IC/UNICAMP |
| Paulo Feofiloff | IME/USP |
| Orlando Lee | IC/UNICAMP |
Suplentes:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Carlos Eduardo Ferreira | IME/USP |