COLORAÇÕES BACKBONE
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
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.