Sobre L(2,1) - Colorações de Classes de Grafos
Autores
|
5662 |
2162,410
|
|
|
5663 |
2162,410
|
Informações:
Publicações do PESC
Uma L(2,1)-coloração é uma atribuição de cores (representadas por números naturais) aos vértices de um grafo onde vértices adjacentes recebem cores que diferem de pelo menos duas unidades e vértices com um vizinho em comum recebem cores diferentes. Esta é ótima quando a maior cor utilizada na atribuição é mínima, neste caso essa cor é denotada por .
Mostramos inicialmente como obter, eficientemente, uma L(2,1)-coloração ótima em grafos split permutação e em grafos (q,q-4) com q fixo, adicionando essas duas classes no seleto grupo em que uma L(2,1)-coloração ótima pode ser encontrada em tempo polinomial. Realizamos então um estudo em grafos aleatórios G(n,p), grafos com b-núcleos limitados e em grafos que são superclasse de árvores, limitando os
possíveis valores para seus .
A seguir, definimos uma L(2,1)-coloração total de um grafo, apresentando uma série de resultados, desde obtenção de soluções eficientes em classes simples até a prova de NP-completude na versão decisão do problema, mesmo quando a entrada é restrita a grafos bipartidos. Surpreendentemente, veri camos a existência de classes de grafos em que as complexidades computacionais da nova versão do problema
diferem da versão clássica.
Ao fim, estabelecemos relações diretas entre uma L(2,1)-coloração e outras colorações de grafos, mostrando também que L(2,1)-coloração quântica é um problema pi-p 2-completo.
An L(2,1)-coloring is an assignment of colors (represented by natural numbers) to the vertices of a graph such that adjacent vertices receive colors that difer by at least two and vertices with a common neighbor receive diferent colors. Such assignment is optimum when the largest used color is minimum, in this case this color is denoted by .
We start by establishing eficient methods to obtain an optimum L(2,1)-coloring on split permutation graphs and (q,q-4) graphs with fixed q, including both in the selected group of classes where one can obtain optimum L(2,1)-coloring in polynomially time. Moreover, we provide a study on random graphs G(n,p), b-core limited graphs, and graphs which are super class of trees, bounding the possible values of on those classes.
Continuing, we define the total L(2,1)-coloring of a graph and we state results such as eficiently optimum total L(2,1)-coloring simple classes of graphs and the NP-completeness proof of the decision version of the problem, even when the instance is restricted to bipartite graphs. Surprisingly, we also show that there are graph classes in which the computational complexity of this new type of assignment completely difers from the classical version, the L(2,1)-coloring.
In the end, we show direct relations among an L(2,1)-coloring and others graph colorings. Furthermore, we verify that a quantum L(2,1)-coloring is a pi p2-complete problem.