Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15966
Título: | Caracterização e coloração de arestas em grafos split-co-comparabilidade |
Título(s) alternativo(s): | Characterization and edge coloring on split-co-comparability graphs |
Autor(es): | Castro, Luis Angelo Loss de |
Orientador(es): | Almeida, Sheila Morais de |
Palavras-chave: | Representações dos grafos Solução de problemas Polinômios Representations of graphs Problem solving Polynomials |
Data do documento: | 13-Jun-2018 |
Editor: | Universidade Tecnológica Federal do Paraná |
Câmpus: | Ponta Grossa |
Citação: | CASTRO, Luis Angelo Loss de. Caracterização e coloração de arestas em grafos split-co-comparabilidade. 2018. 35 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. |
Resumo: | Uma caracterização de um conjunto de grafos é a determinação de propriedades estruturais que identifiquem unicamente os grafos desse conjunto. Essas caracterizações podem dar informações importantes que auxiliam na solução de diversos problemas combinatoriais, como por exemplo, o Problema da Coloração de Arestas. Uma coloração de arestas em um grafo G é uma atribuição de cores para as arestas de G de forma que as cores de quaisquer duas arestas que incidem no mesmo vértice são distintas. O Problema da Coloração de Arestas é determinar o menor número de cores que permite uma coloração de arestas para um dado grafo G. Sabe-se que qualquer grafo simples G tem uma coloração de arestas com _(G) + 1 cores, onde _(G) é o grau máximo do grafo G. Entretanto, alguns grafos G têm uma coloração de arestas com _(G) cores. Decidir se um grafo G tem uma coloração de arestas com _(G) cores é um problema NP completo. Este trabalho apresenta novas caracterizações para os grafos split-co comparabilidade. Usando essas caracterizações, determina-se um subconjunto dos grafos split-co comparabilidade para o qual a versão de decisão do Problema da Coloração de Arestas tem solução em tempo polinomial. |
Abstract: | A characterization of a graph class is the determination of structural properties that uniquely identify the graphs in this class. Those characterizations can give important information that supports many combinatorial problems, such as the Edge Coloring Problem. An edge coloring of a graph G is an assigment of colors to the edges of G such that the colors of any two edges that share a common vertex are distinct. The Edge Coloring Problem is to determine the minimum number of colors that allows an edge coloring for a given graph G. It is known that any simple graph G has an edge coloring with (G)+1 colors, where (G) is the maximum degree of G. However, some graphs G have an edge coloring with (G) colors. It is an NP-complete problem to decide if a graph G has an edge coloring with (G) colors. This work shows new characterizations for split-co-comparability graphs. Using these characterizations, it is determined a subset of split-co-comparability graphs for which the decision version of the Edge Coloring Problem has polynomial time solution. |
URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/15966 |
Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
PG_COCIC_2018_1_04.pdf | 896,3 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.