Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: Resultados Teóricos e Computacionais sobre Coloração Harmoniosa de Grafos

Data: 23/08/2024
Horário: 15h00
Local:  Sala de Reuniões – Bloco 910

Resumo:

Dado um grafo G, uma k-coloração própria dos vértices de G é uma função c : V (G) → {1, . . . , k} de forma que vértices adjacentes não possuem a mesma cor. Uma coloração em vértices de G é dita harmônica quando todo par de cores induz no máximo uma aresta, ou seja, o subgrafo induzido pelos vértices coloridos com tais cores possui no máximo uma aresta. Se a coloração for harmônica e própria, esta é dita harmoniosa. Os problemas de coloração aqui estudados são problemas nos quais o interesse é minimizar o número de cores utilizados em uma coloração harmoniosa de um dado grafo G. Nesta dissertação, realizamos uma revisão bibliográfica dos problemas de coloração harmônica e harmoniosa. O problema de colorações harmônicas que não são necessariamente harmoniosas foi, até então, pouco estudado. Todavia, na revisão, destacamos o único trabalho da literatura que apresenta modelos de programação linear-inteira para o problema de coloração harmônica. No que diz respeito à coloração harmoniosa, além da revisão sobre o tema, apresentamos como novo resultado uma relação, e sua adaptação para digrafos, entre os números cromáticos harmoniosos de um par de grafos (G, H), tal que H é obtido através da identificação de vértices de G que possuem distância maior ou igual a três. Ademais, corrigimos um limitante da literatura para o número cromático harmonioso de grafos d-degenerados. Propomos três novos modelos de programação linear-inteira e apresentamos tabelas com testes sobre instâncias aleatórias e sobre instâncias do segundo “DIMACS Implementation Challenge”. No mais, realizamos um estudo sobre a dimensão dos politopos de dois dos três modelos mencionados.

Banca examinadora:

• Prof. Dr. Júlio César Silva Araújo (MDCC/UFC – Orientador)
• Prof. Dr. Marcio Santos Costa (UFMG – Coorientador)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
• Prof. Dr. Fabricio Siqueira Benevides (UFC)