O Método de Distribuição de Cargas

Abstract

Este trabalho apresenta um estudo sobre o Método de Distribuição de Cargas, procurando exibir com clareza os principais aspectos desta técnica. O principal objetivo é iniciar o leitor ao estudo deste método. Este trabalho tem como propósito ser simples e didático. Apresentamos a formulação geral, alguns exemplos bem simples, três problemas mais completos e várias referências bibliográficas relevantes em relação ao assunto. Mostramos resultados obtidos para o problema da 3-coloração de vértices relacionado á conjectura de Steinberg que ainda está em aberto, para o problema da Coloração Simultânea de Grafos Imersos e para o problema da Simetria em Grafos. Com exceção do problema da 3-coloração, os resultados apresentados são os melhores possíveis. Para o problema da 3-coloração, os melhores resultados possuem um grau de dificuldade alto, fugindo do escopo deste trabalho.

This work presents the Discharging Method in graph theory. We try to show with clarity the main aspects of this technique. The main objective is to introduce the reader to the study of this method. This work intends to be simple and didactic. We present the general formulation, some very simple examples, three more important problems and an excellent bibliography related to the subject. More precisely, we present the main results for the following problems: the vertex 3-coloring problem related to a conjecture of Steinberg that is still open, the simultaneous coloring of immersed graphs problem, and the symmetry of graphs problem. Except for the vertex 3-coloring problem, the presented results are the best possible. The best result for the vertex 3-coloring problem has a high degree of dificulty and is out of the scope of this work.