Fluxos inteiros e colorações

Esta tese trata de fluxos inteiros e colorações em grafos, problemas intimamente relacionados. Concentramos nossa atenção nas Conjeturas de Tutte sobre 5-, 4- e 3-fluxos, as quais foram propostas entre as décadas de 50 e 70 e permanecem abertas até hoje. Apresentamos três abordagens para o ataque das conjeturas, com ênfase na Conjetura dos 3-Fluxos. Na primeira abordagem propomos o estudo dos grafos fluxo-críticos, aqueles que não admitem um k-fluxo, mas que passam a admitir quando sujeitos a uma simples operação de redução. O interesse no estudo dessa classe de grafos vem da observação de que todo contra-exemplo mínimo para qualquer uma das conjeturas de Tutte é fluxo-crítico. Na segunda abordagem estudamos a conexidade cíclica do contra-exemplo mínimo para uma conjetura equivalente à Conjetura dos 3-Fluxos. Na terceira abordagem buscamos uma nova demonstração do Teorema de Grötzsch, o qual é o dual planar da Conjetura dos 3-Fluxos, que não utilize a Fórmula de Euler como a demonstração original. (AU)