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.Publicado
2019-01-14
Edição
Seção
XXXVII Encontro de Iniciação Científica
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.