A conjetura dos 3-fluxos de Tutte e emparelhamentos em grafos bipartidos

A dissertação aborda o tema de fluxos inteiros em grafos e, mais especificamente, a Conjetura dos 3-fluxos de Tutte, a qual postula que todo grafo 4-aresta-conexo admite um 3-fluxo. Motivados pela existência de uma redução da Conjetura dos 3-fluxos para grafos 5-regulares, concentramos nosso trabalho no estudo das propriedades dos grafos 5-regulares que admitem 3-fluxo. Como resultado, estabelecemos que tais grafos são caracterizados pela existência de uma equipartição de seus vértices com certas propriedades especiais, a qual denominamos equipartição mod 3-orientável. Por sua vez, caracterizamos equipartições mod 3-orientáveis de duas formas: (i) pela existência de um emparelhamento perfeito em um grafo bipartido derivado da equipartição e (ii) em termos do tamanho dos cortes de arestas do grafo. Tais caracterizações dão origem a um algoritmo polinomial para determinar se uma dada equipartição de um grafo 5-regular é mod 3-orientável