Autores

4836
410,2162
4837
410,2162

Informações:

Publicações do PESC

Título
L(2,1) - Colorações: Algoritmos e Limites Superiores em Classes de Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
21/9/2009
Resumo

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.

Abstract

The L(2,1)-coloring problem, also known as  ?-coloring, is a variant of the vertex coloring of a graph where adjacent vertices get colors (represented by natural numbers) which differ by at least two and non-adjacent vertices having a common neighbor get different colors. The aim is to minimize the span, that is, the greatest assigned color.
 
This dissertation presents a survey on the main results on this problem, containing a proof of its NP-completeness, exponential-time algorithms for general graphs, linear-time algorithms for specific classes of graphs, and upper bounds for the span for general graphs as well as for graphs belonging to specific classes.
 
Moreover, new results are presented including a linear-time algorithm for P4-tidy graphs, upper bounds for weakly chordal graphs, line graphs and chordal bipartite graphs, and improvements of known upper bounds for, among others, split graphs, permutation graphs and cographs.

Arquivo
Topo