Coloração de arestas em grafos split-comparabilidade e split-intervalos
Ano de defesa: | 2021 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | , , , |
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
|
Departamento: |
Não Informado pela instituição
|
País: |
Brasil
|
Palavras-chave em Português: | |
Área do conhecimento CNPq: | |
Link de acesso: | http://repositorio.utfpr.edu.br/jspui/handle/1/25776 |
Resumo: | Uma coloração de arestas própria de um grafo é uma atribuição de cores para as suas arestas tal que arestas incidentes em um mesmo vértice têm cores distintas. O Problema da Coloração de Arestas é responder, dado um grafo, qual o menor número de cores para uma coloração de arestas própria. Esse número é chamado de índice cromático e, para um grafo , é denotado por ′(). Por definição, o índice cromático é pelo menos ∆(), onde ∆() é o maior número de arestas incidentes em um mesmo vértice do grafo . Em 1964, Vizing provou que ′() ≤ ∆() + 1 para qualquer grafo simples . Portanto, quando é simples, ∆() ≤ ′() ≤ ∆() + 1. Um grafo é Classe 1 se o seu índice cromático é igual ao seu grau máximo, e é Classe 2 caso contrário. O Problema da Classificação é decidir se um grafo simples é Classe 1. A despeito de haver apenas dois possíveis valores para o índice cromático de um grafo simples, o Problema da Classificação é NP-completo. Em 1985, em sua famosa coluna "The NP-Completeness Column: an Ongoing Guide”, David Johnson classificou alguns problemas da Teoria dos Grafos em relação à sua complexidade computacional. Em alguns casos, esta complexidade ainda era desconhecida e Johnson identificou classes de grafos para as quais considerou que seria fácil determiná-la. Nas classes de grafos split, de comparabilidade e de intervalos, por exemplo, Johnson considerou que determinar a complexidade computacional do Problema da Classificação era possivelmente fácil. Entretanto, após 35 anos, apenas a complexidade computacional do Problema da Classificação para os grafos de comparabilidade foi determinada, sendo este um problema NP-completo. Esta dissertação apresenta uma solução de tempo polinomial para o Problema da Classificação para grafos split-intervalos, além de identificar e corrigir um problema na prova que determina o índice cromático dos grafos split-comparabilidade. |