Sobre L(2,1) - Colorações de Generalizações de Árvores
Autores
|
5907 |
2726,410
|
|
|
5908 |
2726,410
|
Informações:
Publicações do PESC
Título
Sobre L(2,1) - Colorações de Generalizações de Árvores
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
8/12/2015
Resumo
Uma L(2,1)-coloração de um grafo é uma atribuição de inteiros não negativos, também referidos como cores, a seus vértices tal que vértices adjacentes recebem cores cuja diferença é pelo menos dois e vértices com um vizinho em comum recebem cores diferentes. A diferença entre a maior e a menor cor atribuída é denominada o comprimento da L(2,1)-coloração. O problema da L(2,1)-coloração consiste em calcular o número L(2,1)-cromático de um dado grafo, que equivale ao menor dentre os comprimentos de todas as suas L(2,1)-colorações. Inspirada na prova do limite superior justo para o número L(2,1)-cromático de árvores, esta dissertação trata de limites superiores para o número L(2,1)-cromático em classes de grafos que são generalizações da classe das árvores: k-árvores, cactos e grafos de blocos. Para cada uma destas classes, apresentamos os limites superiores conhecidos na literatura e limites superiores menores (ou iguais nos casos em que o limite conhecido já é justo) obtidos neste trabalho.
Abstract
An L(2,1)-colouring of a graph is an assignment of nonnegative integers, also referred to as colours, to its vertices such that adjacent vertices receive colours at least two apart and vertices with a common neighbour receive diferent colours. The diference between the largest assigned colour and the smallest assigned colour is the span of the L(2,1)-colouring. The problem of the L(2,1)-colouring consists in computing the L(2,1)-chromatic number of a given graph, which is equivalent to the smallest among the spans of all the L(2,1)-colourings of the graph. Inspired by the proof of the tight upper bound for the L(2,1)-chromatic number of trees, this dissertation deals with upper bounds for the L(2,1)-chromatic number on graph classes which are generalizations of the class of the trees: k-trees, cacti and block graphs. For each of these classes, we present the upper bounds known from the literature and present smaller upper bounds (or equal ones in the cases in which the known bound is already tight) obtained in this work.
Arquivo