Caracterização e coloração de arestas em grafos split-co-comparabilidade

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorQueiroz, Saulo Jorge Beltrão de-
Autor(es): dc.contributorMatos, Simone Nasser-
Autor(es): dc.creatorCastro, Luis Angelo Loss de-
Data de aceite: dc.date.accessioned2022-02-21T21:49:11Z-
Data de disponibilização: dc.date.available2022-02-21T21:49:11Z-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2018-06-13-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/15966-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/661261-
Descrição: dc.descriptionA 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.-
Descrição: dc.descriptionUma 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherDepartamento Acadêmico de Informática-
Publicador: dc.publisherCiência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectRepresentações dos grafos-
Palavras-chave: dc.subjectSolução de problemas-
Palavras-chave: dc.subjectPolinômios-
Palavras-chave: dc.subjectRepresentations of graphs-
Palavras-chave: dc.subjectProblem solving-
Palavras-chave: dc.subjectPolynomials-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleCaracterização e coloração de arestas em grafos split-co-comparabilidade-
Título: dc.titleCharacterization and edge coloring on split-co-comparability graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.