Colorações distintas nos vértices adjacentes em potências de caminho

• Ano de defesa: 2018
• Autor(a) principal: Omai, Mayara Midori
• Orientador(a): Almeida, Sheila Morais de
• Banca de defesa: Guedes, André Luiz Pires, Machado, Raphael Carlos Santos, Carmo, Renato José da Silva, Almeida, Sheila Morais de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Ponta Grossa
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação
• País: Brasil
• Palavras-chave em Português: Teoria dos grafos; Representações dos grafos; Computação; Cores - Análise; Graph theory; Representations of graphs; Computer science
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/3804

Em um grafo, dois elementos são adjacentes se são um par de vértices que constituem uma aresta, ou se são duas arestas que contêm um mesmo vértice, ou se são uma aresta e um dos vértices que a compõem. Uma coloração de um grafo consiste na atribuição de cores para seus elementos (vértices, ou arestas, ou vértices e arestas). Dado um grafo colorido, o conjunto de cores de um vértice , denotado por (), é composto pelas cores das arestas incidentes em e do próprio quando colorido. O Problema da Coloração de Arestas Distinta nos Vértices Adjacentes consiste em apresentar uma coloração de arestas utilizando o menor número de cores de forma que arestas adjacentes tenham cores distintas e para toda aresta , () ̸= (). O Problema da Coloração Total Distinta nos Vértices Adjacentes consiste em apresentar uma coloração total utilizando o menor número de cores de forma que elementos adjacentes tenham cores distintas e para toda aresta , () ̸= (). Nesta dissertação apresentamos a solução do problema da coloração de arestas distinta nos vértices adjacentes e do problema da coloração total distinta nos vértices adjacentes quando restritos às potências de caminho.