M2-COLORAÇÃO DE ARESTAS E EMPARELHAMENTO MÁXIMO

Resumo

Sejam grafos estruturas G: (V,E) tais que V é um conjunto não-vazio de objetos denominados vértices (ou nós) e E é um subconjunto de pares não-ordenados de V. Uma coloração de arestas C é uma função f de E em C, onde C é chamado conjunto de cores. É conhecido que o problema geral de coloração de arestas, que coniste em determinar o menor número de cores que podem ser atribuídas às arestas do grafo de forma que arestas vizinhas não possuam cor comum, é considerado computacionalmente difícil (NP-completo). Se a cardinalidade do conjunto de cores das arestas incidentes a cada vértice v é no máximo i, a coloração é dita uma Mi-coloração de arestas. Neste trabalho, focamos nos resultados conhecidos para i=2, o que é chamado de M2-coloração de arestas. Seja um emparelhamento um conjunto de arestas de G sem nenhuma extremidade em comum e seja a(G) o tamanho do emparelhamento máximo. Todo grafo com grau máximo pelo menos 2 possui uma M2-coloração de arestas com pelo menos a(G)+1 cores. Foi estudado que para todo n pertencente aos naturais e grafos com grau mínimo iguais a 1, 2, 3, 4 ou 5 existe um grafo planar conexo G com pelo menos n vértices com grau mínimo entre os valores apresentados acima tal que o número maximo de cores ultilizadas em uma M2-coloração de arestas é dado por a(G)+1. Tambem existem resultados para grafos triangulados de grau minimo 3, 4 ou 5. O problema principal deste trabalho consiste em determinar o maximo de cores Ki em uma M2-coloração de arestas de um grafo G.