L(2, 1)-coloração de k-árvores e grafos com treewidth limitado

Abstract

Uma L(2, 1)-coloração de um grafo G = (V, E) é uma atribuição f de inteiros n˜ao- negativos em V tal que, se uv ∈ E, então |f (u) − f (v)| ≥ 2; al´em disso, se uv ∈ E, vw ∈ E e u /= w, então f (u) /= f (w). O span de f ´e o maior inteiro utilizado, e λ ´e o menor span dentre os de todas as L(2, 1)-colorações de G. Neste trabalho, melhoramos a cota superior conhecida para λ em k-´arvores e fornecemos uma cota superior alternativa para λ em grafos com treewidth limitado. Nossos resultados restringem possí contraexemplos para a conjectura de Griggs e Yeh, a qual afirma que λ ≤ ∆2 para todo grafo com ∆ ≥ 2.