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

• Ano de defesa: 2021
• Autor(a) principal: Gonzaga, Luis Gustavo da Soledade
• Orientador(a): Almeida, Sheila Morais de
• Banca de defesa: Almeida, Sheila Morais de , Miranda, Alberto Alexandre Assis , Sales, Claudia Linhares , Zatesko, Leandro Miranda
• 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
• País: Brasil
• Palavras-chave em Português: Representações dos grafos; Teoria dos grafos; Cores; Algorítmos computacionais; Representations of graphs; Graph theory; Colors; Computer algorithms
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/25776

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.