A COLORAÇÃO DE GRUNDY PARCIAL

Resumo

Em teoria dos grafos, coloração de grafos é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Existem ao menos seis variações de problemas de coloração baseados em heurísticas, entre elas focamos em estudar a coloração de Grundy (ou coloração gulosa) e a coloração de Grundy parcial. Uma coloração de Grundy de um grafo G é uma coloração obtida aplicando o algoritmo guloso de acordo com alguma ordem dos vértices de G. Enquanto que uma coloração de Grundy parcial é uma coloração em que ao menos um vértice em cada classe de cor é colorido de maneira gulosa. O número de Grundy (parcial) é então o maior inteiro k para o qual G admite uma coloração gulosa (parcial) com k cores. Neste trabalho, estamos interessados em identificar que resultados válidos para as colorações de Grundy continuam valendo para as colorações de Grundy parcial. Em particular, nos interessamos nos resultados envolvendo produtos de grafos. Já obtivemos resultados envolvendo o número de Grundy parcial do produto lexicográfico de grafos. Tais resultados foram apresentados no VI Encontro de Teoria da Computação (ETC) do XLI Congresso da Sociedade Brasileira de Computação (CSBC 2021), trabalho intitulado "Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs", em coautoria com Yuri Silva de Oliveira e a professora coordenadora do projeto. Destacamos que o trabalho recebeu o prêmio de segundo melhor trabalho apresentado. Agradece-se ao CNPq pelo apoio financeiro.