64ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 16. Teoria da Computação

L(2,1)-COLORAÇÃO EM SUPERCLASSES DE ÁRVORES

Gabriel Ferreira Barros 1 Márcia Rosana Cerioli 2,3 Daniel Fabio Domingues Posner 4

1. Bacharelado em Ciência da Computação - Universidade Federal do Rio de Janeiro 2. Profa. Dra./Orientadora Instituto de Matemática 3. PESC/COPPE - Universidade Federal do Rio de Janeiro 4. Candidato D.Sc./Colaborador - PESC/COPPE - Universidade Federal do Rio de Janeiro

INTRODUÇÃO:

Um grafo G é um par de conjuntos (V, E), onde V é finito e não-vazio, e E consiste de pares não-ordenados de elementos de V. Uma coloração de G é uma função f com domínio V e contradomínio os inteiros não-negativos tal que, se {u, v} pertence a E, então f(u) é diferente de f(v). Uma L(2,1)-coloração de G é uma coloração f tal que, se {u, v} pertence a E, então f(u) e f(v) diferem de pelo menos duas unidades e, se u e v estão a distância dois, então f(u) é diferente de f(v). O maior inteiro usado é seu span. O problema da L(2,1)-coloração consiste em, dado um grafo, encontrar seu span mínimo. Este problema em sua versão decisão é NP-completo e há uma conjectura de que o span mínimo tem como limite superior o quadrado do maior grau do grafo. A motivação deste tipo de coloração veio da pesquisa na atribuição eficiente de frequências de canais a radiotransmissores, visando evitar interferências. Focando em superclasses de árvores, neste trabalho, melhoramos as cotas superiores existentes para o span mínimo em k-árvores e cacti e estabelecemos um limite superior alternativo para o span mínimo em grafos com treewidth limitado. Para uma subclasse de grafos blocos, encontramos condições suficientes e condições necessárias para o span mínimo ser o grau máximo mais um.

METODOLOGIA:

Realizamos uma ampla pesquisa bibliográfica, destacando o artigo de Griggs e Yeh (Jerrold R. Griggs e Roger K. Yeh. Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595, 1992), onde definiram o problema da L(2,1)-coloração e provaram sua NP-completude, além de estabelecerem a conjectura referente ao limite superior para o span de grafos em geral. Em nossa pesquisa, fizemos o levantamento de técnicas já utilizadas para a obtenção de limites superiores para o valor do span mínimo em algumas classes de grafos. Além disso, fizemos um levantamento de classes de grafos interessantes tanto teoricamente, quanto com aplicações no mundo real, e aplicação das técnicas catalogadas nestas classes. Utilizando estes resultados, tentamos estabelecer novos limites superiores e inferiores para classes de grafos ainda não pesquisadas, ou melhorar limites já estabelecidos, além da busca de exemplares que justifiquem estas cotas. Por fim, uma outra meta foi desenvolver algoritmos eficientes para a resolução do problema.

RESULTADOS:

Um grafo é: (i) árvore se é conexo e acíclico; (ii) k-árvore se é um grafo completo com k vértices ou se pode ser obtido de uma k-árvore adicionando um vértice simplicial de grau k; (iii) grafo bloco se é conexo e seus componentes biconexos são cliques; (iv) cactus se toda aresta está em, no máximo, um ciclo. O treewidth de um grafo é o menor inteiro k para o qual é ele é subgrafo de uma k-árvore. Fazendo uma análise mais detalhada da cota superior existente para o span mínimo em k-árvores, obtivemos uma redução desta cota de ordem quadrática no valor de k. Utilizando uma variação do algoritmo de McDiarmid, estabelecemos uma cota superior alternativa para o span mínimo em grafos com treewidth limitado. Em relação à cota já existente, esta cota é menor em diversos casos, e, a partir dela, obtém-se uma restrição melhor para possíveis contra-exemplos da conjectura de Griggs e Yeh. Seja B a subclasse dos grafos blocos obtidos a partir de árvores T, adicionado um vértice w adjacente aos vértices u e v para cada aresta {u, v} de T. Determinamos o valor exato do span mínimo em grafos de B sob determinadas condições. Para cacti, mostramos limites superiores para o span mínimo em função da cintura. Além disso, exibimos exemplos de grafos nesta classe que atingem as cotas encontradas.

CONCLUSÃO:

Os objetivos deste estudo foram alcançados já que, não somente entendemos os resultados já existentes na literatura sobre o assunto, como em vários casos, conseguimos melhorá-los. Os resultados obtidos durante este trabalho forneceram novos limites superiores para o valor do span mínimo em diversas superclasses de árvores. Em especial, o estudo na subclasse dos grafos blocos forneceu uma visão sobre uma variante do problema da L(2,1)-coloração de vértices. Nesta, os vértices e as arestas recebem inteiros não-negativos respeitando as mesmas restrições do problema. Desta forma, a subclasse de blocos estudada nos dá resultados para este novo tipo de L(2,1)-coloração na classe das árvores. Pretendemos continuar o estudo nessa subclasse de blocos a fim de estabelecer novos resultados para essa variação de L(2,1)-coloração nas árvores. Além disso, procuramos estudar cotas superiores para o valor do span mínimo em outras classes relacionadas, como grafos linha de árvore e desenvolver um algoritmo eficiente para determinar o span mínimo em cacti.

Palavras-chave: Teoria de grafos, L(2,1)-coloração, árvores.