Coloração de arestas em grafos split-comparabilidade e split-intervalos - Gonzaga, Luis Gustavo da Soledade (2021)
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.