Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/10416
Título: Coloração arco-íris para cografos
Título(s) alternativo(s): Rainbow coloring for cographs
Autor(es): D’Almeida, Diego Gonzales
Orientador(es): Almeida, Sheila Morais de
Palavras-chave: Cores
Grafos de ligação
Arco-íris
Colors
Bond graphs
Rainbow
Data do documento: 20-Nov-2018
Editor: Universidade Tecnológica Federal do Paraná
Câmpus: Ponta Grossa
Referência: D’ALMEIDA, Diego Gonzales. Coloração arco-íris para cografos. 2018. 40 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018.
Resumo: Uma coloração de arestas consiste na atribuição de cores às arestas do grafo. Uma forma de atribuição para essas cores é a coloração arco-íris. Essa coloração tem por característica a existência de um caminho que não repete cores entre cada par dos vértices do grafo - chamado de caminho arco-íris. O Problema da Coloração Arco-Íris consiste em encontrar o menor número de cores k para qual um grafo G possui uma coloração arco-íris. Esse k mínimo é chamado de número de conexão arco-íris e é denotado por rc(G). O Problema da Coloração Arco-Íris é NP-Completo. Poucas classes de grafos possuem um algoritmo eficiente conhecido para determinar rc(G). Este trabalho apresenta limitantes superiores justos para o número de conexão arco-íris em cografos, que são caracterizados por não possuírem Ρ4 induzido.
Abstract: An edge coloring of a graph is a assignment of colors to the edges of the graph. The rainbow coloring is an assignment of these colors such that for every pair of vertices there is a path that does not repeat colors. These paths are called rainbow paths. The Rainbow Coloring Problem consists in determining the least number of colors for a rainbow coloring of a given graph. This minimum number of colors is known as rainbow connection number and it is denotes by rc(G) for a graph G. The rainbow coloring Problem is NP-complete. There are efficient algorithms to solve it for few classes of graphs. This work presents a tight upper bound for the rainbow connection number of cographs, which are graphs without induced Ρ4.
URI: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/10416
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2018_2_08.pdf622,49 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.