Título: Heurísticas para coloração k-imprópria

Data: 20/09/2019

Horário: 13:00h

Local: Sala de reuniões, bloco 910

Resumo:

Uma coloração dos vértices de um grafo $G = (V,E)$ é própria se vértices adjacentes recebem cores diferentes. Estudamos neste trabalho uma relaxação desse problema onde, dado um inteiro positivo $k$, é possível que um vértice e no máximo $k$ de seus vizinhos compartilhem a mesma cor. Uma vez que, como a coloração clássica, a coloração $k$-imprópria é um problema difícil, pode-se abordar o problema através do uso de heurísticas. Neste trabalho, introduzimos o número guloso $k$-impróprio de um grafo e investigamos esse parâmetro em árvores binomiais e em cografos. As definições e conceitos de $b$-coloração são generalizados para o contexto de coloração imprópria. Mostramos que a aplicação da estratégia de $b$-coloração imprópria pode não convergir. Por fim, apresentamos formulações dos problemas de coloração gulosa própria e imprópria.

Banca:

• Prof. Dra. Cláudia Linhares Sales (MDCC/UFC - Orientadora)
• Prof. Dra. Ana Karolinna Maia de Oliveira (UFC)
• Prof. Dr. Manoel Bezerra Campelo Neto (UFC)
• Prof. Dr. Tibérius de Oliveira e Bonates (UFC)