Coloração de arestas em grafos split-comparabilidade e split-intervalos

Detalhes bibliográficos
Ano de defesa: 2021
Autor(a) principal: Gonzaga, Luis Gustavo da Soledade lattes
Orientador(a): Almeida, Sheila Morais de lattes
Banca de defesa: Almeida, Sheila Morais de lattes, Miranda, Alberto Alexandre Assis lattes, Sales, Claudia Linhares lattes, Zatesko, Leandro Miranda lattes
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.