Coloração de Arestas

Coloração de Arestas – Teorema de Vizing
Anny Beatriz Navarro, Marcelo Vassoler, Thays A. Fabri
Bacharelado em Ciência da Computação – Universidade Tecnológica Federal do Paraná
(UTFPR)
CEP84016-210 – Ponta Grossa – PR – Brasil [e-mail],[e-mail], [e-mail]

Abstract. The graph coloring problems is one of the most well known in graph theory. The problem is a graph coloring so that all edges adjoining a vertex are of different colors, but one must use the smallest number of possible colors. There are a number of theorems which enables coloring the edges of a graph in different ways. The focus of the article is that Vizing's theorem states that a simple graph can have all its edges properly colored with the largest number of edges that fall within the same verse in another color graph.
Resumo: A coloração de grafos é um dos problemas mais conhecidos na teoria dos grafos. O problema consiste em colorir um grafo de forma que todas as arestas adjacentes de um vértice sejam de cores diferentes, porém deverá ser usado o menor número de cores possíveis. Existem vários teoremas que possibilitam colorir as arestas de um grafo de formas diferentes. O enfoque do artigo é o Teorema de Vizing que afirma que um grafo simples pode ter todas as suas arestas devidamente coloridas com o maior número de arestas que incidem no mesmo verso dentro do grafo mais uma cor.

1. Coloração de Arestas
A coloração de arestas de um grafo, nada mais é que atribuições de cores sem que haja arestas adjacentes de mesmas cores. Mas qual é a utilidade da coloração de arestas? E por que muitas pessoas trabalham em estudos nessa área? Com a lógica de coloração de arestas podemos resolver muitos problemas reais, quanto menor a quantidade de cores que usamos na coloração de arestas de um grafo é menos recursos sendo gastos em problemas reais. Por exemplo, você está organizando jogos de futebol, em vários estádios, com vários times e