L(2,1) - Colorações: Algoritmos e Limites Superiores em Classes de Grafos

O problema da L(2,1)-coloração, também chamado de ?-coloração, é uma variação do problema de coloração de vértices de um grafo, onde vértices adjacentes recebem cores (representadas por números naturais) com diferença de pelo menos dois e vértices não adjacentes, mas que tenham um vértice em comum em suas vizinhanças, recebem cores diferentes. O objetivo é minimizar o span, ou seja, a maior cor utilizada.
 
Esta dissertação apresenta uma coletânea dos principais resultados sobre este problema contendo, uma prova de sua NP-completude, algoritmos exponenciais para grafos em geral, algoritmos lineares para classes específicas de grafos e limites superiores para o span, tanto de grafos em geral, quanto de grafos pertencentes a classes específicas.

Além disso, são apresentados resultados novos que incluem um algoritmo linear para a classe dos grafos P4-tidy, o estabelecimento de limites superiores para grafos fracamente cordais, grafos linha e grafos bipartido cordais e a melhoria dos limites superiores conhecidos para grafos split, permutação, cografos, entre outros.