Produção Nacional
L(2, 1)-coloração de k-árvores e grafos com treewidth limitado
2015; Linguagem: Português
10.5540/03.2015.003.01.0241
ISSN2359-0793
AutoresGabriel F. Barros, Daniel Posner, Márcia R. Cerioli,
Tópico(s)Graph Labeling and Dimension Problems
ResumoUma 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.
Referência(s)