COLORAÇÕES BACKBONE

Autores

  • Camila Sena Araujo
  • Julio Cesar Silva Araujo

Resumo

Um grafo é um par G=(V,E) onde V=V(G) é um conjunto não-vazio finito, cujos elementos são chamados de vértices, e E=E(G) é uma família de subconjuntos de V, chamados de arestas, com dois elementos. Através deste objeto combinatório, é possível estudar diversos problemas em que se tem um certo conjunto de objetos e se quer analisar relações entre estes objetos. Pela imensa quantidade de aplicações para esse tipo de problema, surgiu um novo ramo na matemática, a Teoria dos Grafos, que possui também uma forte ligação com outras áreas, como Topologia, Análise e Álgebra. Em uma das classes de problemas mais conhecidas dessa área, encontram-se os problemas de coloração, onde deseja-se determinar o número cromático de uma determinada classe de grafos, isto é, o menor número de cores para o qual pode-se colorir os vértices de um grafo de modo que os vértices de qualquer aresta não recebem a mesma cor. Formalmente, uma k-coloração própria de vértices é definida como uma função c:V(G)->{1,2,...,k}, onde |(c(v)-c(u)|>0 quando {u,v} pertence a E(G). Neste trabalho, estudou-se uma variação do problema de coloração conhecida como coloração backbone. Dado um par de grafos (G,H), onde H é subgrafo de G, uma k-coloração q-backbone de (G,H) é uma função c:V(G)->{1,...,k} onde c é uma k-coloração própria de V(G) e |(c(v)-c(u)|>q-1 quando {u,v} pertence a E(H). Denota-se por BBCq(G,H) o menor inteiro k para o qual existe uma k-coloração q-backbone de (G,H). Também generalizou-se tal coloração para uma métrica circular sobre o anel dos inteiros módulo k, onde denota-se por CBCq(G,H) o menor inteiro k para o qual existe uma k-coloração q-backbone de (G,H) nessa métrica. Os resultados obtidos durante o projeto estão relacionados com o valor de BBCq(G,H) e CBCq(G,H) sob ponto de vista de otimização e complexidade, onde buscou-se um limitante superior para ambos quando G e H pertencem a determinadas classes de grafos. Agradece-se ao CNPq pelo apoio financeiro.

Publicado

2019-01-14

Edição

Seção

XXXVII Encontro de Iniciação Científica