Coloração k-imprópria gulosa

• Ano de defesa: 2020
• Autor(a) principal: Rodrigues, Efraim Naassom Helem Dantas
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Coloração gulosa; Coloração defectiva; Coloração imprópria; Árvores binomiais; Cografos; Programação matemática
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/50955

A vertex coloring of a graph G= (V,E) is proper if adjacent vertices have distinct colors. In this work, we study a relaxation of this problem, called k-improper coloring, in which, given a positive integer k, each vertex can share its color with at most k neighbors. Since the proper coloring problem is a 0-improper coloring, this relaxation is as difficult as the classic coloring problem, and thus it can be approached by the means of heuristics. Here, we introduce the k-improper version of the greedy coloring heuristic. As usual, we aim to estimate the worst case of this heuristic. Besides introducing the k-improper Grundy Number, we generalized the concept of t-atoms as well as we investigated the k-improper Grundy Number for binomial trees and cographs, and presented mathematical programming formulations for the improper and proper Grundy Number (fulfilling a gap in this study).