Coloração Total em Grafos Potência de Ciclo
Autores
|
6692 |
257,2999,2092
|
|
|
6691 |
257,2999,2092
|
|
|
6693 |
257,2999,2092
|
Informações:
Publicações do PESC
Um grafo Potência de Ciclo Ckn é um grafo obtido de um ciclo sem cordas Cn adicionando arestas entre todos os vértices à distância de no máximo k. Os grafos Potência de Ciclo têm sido extensivamente estudados na literatura, principalmente quando tratamos de problemas de coloração. Problemas clássicos, como Coloração de Vértices e Coloração de Arestas, foram totalmente resolvidos nos grafos Potência de Ciclo [7, 32]. Entretanto, o problema da Coloração Total permanece aberto para esta classe de grafos. E mesmo que os trabalhos de Campos e de Mello [9] e de Almeida et al. [1] mostrem avanços significativos para valores específicos de n e k, o problema da Coloração Total está longe de ser resolvido para a classe. Uma conjectura notável, proposta por Campos e de Mello [9], estabelece que Ckn, com 2 =< k < b (n/2), é Tipo 2 se e somente se n é ímpar e n < 3(k + 1), caso contrário é Tipo 1. Em particular, esta conjectura implica que, para cada k >= 2, o número de grafos Tipo 2 é finito e que todo grafo Potência de Ciclo Ckn, com n >= 3(k + 1), é Tipo 1. No presente trabalho, mostramos que todo grafo Potência de Ciclo com k par, k >= 2 e n >= 4k2 + 2k é Tipo 1. Além disso, utilizando a mesma técnica, classificamos todos os grafos Potência de Ciclo Ckn, com k = 3 e k = 4 e também obtemos um limitante para que os grafos Potência de Ciclo Ckn, com k = 5 e k = 7, sejam Tipo 2. Também apresentamos um algoritmo para gerar uma Coloração Harmônica Equilibrada para os grafos Potência de Ciclo Ckn, com n par ou n ímpar e n >= 3(k + 1), em um passo necessário para a construção de uma Coloração Total Equilibrada Tipo 1. Ademais, apresentamos uma família infinita de grafos Potência de Ciclo em que a Coloração Total Equilibrada é ótima.
A power of cycle graph Ckn is the graph obtained from the chordless cycle Cn by adding an edge between any pair of vertices of distance at most k. Power of cycle graphs have been extensively studied in the literature, in particular with respect to coloring problems, and both vertex-coloring and edge-coloring problems have been solved in the class. The total-coloring problem, however, is still open for power of cycle graphs. Although recent works from Campos and de Mello [9] and from Almeida et al. [1] point partial results for specific values of n and k, the totalcoloring problem is far from being solved in the class. One remarkable conjecture from Campos and de Mello [9] states that Ckn, with 2 =< k < (n/2), is Type 2 if and only if n is odd and n < 3(k + 1). In particular, the conjecture would imply that, for each k >= 2, the number of Type 2 graphs is finite and every power of cycle graph Ckn with n >= 3(k+1) would be Type 1. We show that for even power of cycle graphs Ckn with k >= 2 and n >= 4k2 + 2k are Type 1. Moreover, our proof also classifies the graphs power of cycle Ckn, with k = 3 and k = 4, and also shows a threshold for the graphs Ckn, with k = 5 and k = 7, to be Type 2. We also present a framework to decompose any power of cycle graph into two other power of cycles, an algorithm to generate an equitable conformable total coloring for all the graphs power of cycle that possibly have a equitable total coloring, and an infinite family of power of cycle graphs that have an optimal equitable total coloring.