Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15977| 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 |
| Citação: | 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.utfpr.edu.br/jspui/handle/1/15977 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PG_COCIC_2018_2_08.pdf | 622,49 kB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.