Fluxos inteiros e colorações

Autor(es)

Candida Nunes da Silva

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2009-04-12

Membros da banca

Cláudio Leonardo Lucchesi; Daniel Harven Younger; Marcelo Henriques de Carvalho; Arnaldo Mandel; Paulo Feofiloff; Orlando Lee

• Orientador: Cláudio Leonardo Lucchesi

Resumo

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)

• Processo FAPESP: 02/05665-6 - Conjeturas de tutte e emparelhamentos em grafos bipartidos.
• Beneficiário: Candida Nunes da Silva
• Modalidade de apoio: Bolsas no Brasil - Doutorado