Nowhere-zero flows and colorings of graphs / Fluxos inteiros e colorações
AUTOR(ES)
Candida Nunes da Silva
DATA DE PUBLICAÇÃO
2009
RESUMO
The theme of this thesis is nowhere-zero flows and colourings of graphs, two subjects that are closely related. We focus mainly on the three Conjectures of Tutte concerning 5-, 4- and 3-nowhere-zero flows. These conjectures were proposed, respectively, in the 50 s, 60 s and 70 s; all of them remain open so far. In this thesis we present three different approaches for the study of Tutte s Conjectures, with emphasis on the 3-Flow Conjecture. In the first approach, we introduce the concept of flow-critical graph. A graph is flowcritical if it does not admit a nowhere-zero k-flow but, when a simple reduction operation is applied, the resulting graph does admit a nowhere-zero k-flow. The motivation for the study of such graphs is due to the observation that any minimum counterexample for any of Tutte s conjectures lies in this particular class. In the second approach, we study the cyclic-connectivity of a minimum counterexample for an equivalent version of the 3-Flow Conjecture. In the third approach, we give a new proof for Gr¨otzsch s Theorem that differs from the original in the fact that it does not depend on Euler s Formula
ASSUNTO(S)
teoria dos grafos graph theory computer theory teoria da computação
