Coloração de identificação local no produto corona de ciclos e caminhos
Resumo
Uma coloração de identificação local (lid-coloração) em um grafo é uma coloração própria tal que para qualquer aresta uv, se u e v têm vizinhanças fechadas distintas, então o conjunto de cores utilizadas sobre os vértices das vizinhanças fechadas de u e v são distintos. O número lid-cromático do grafo G, denotado por χlid(G), é o menor número de cores necessárias em qualquer lid-coloração de G. Neste trabalho, determinamos o número lid-cromático do produto corona em que os fatores são grafos bipartidos e também quando são ciclos e/ou caminhos, onde pelo menos um dos fatores não é bipartido. Além disso, fornecemos alguns limites inferiores para o número lid-cromático do produto corona de dois grafos.
Referências
Bhyravarapu, S., Kumari, S., and Reddy, I. V. (2023). On locally identifying coloring of graphs. In Conference on Algorithms and Discrete Applied Mathematics, pages 147–158. Springer.
Esperet, L., Gravier, S., Montassier, M., Ochem, P., and Parreau, A. (2012). Locally identifying coloring of graphs. The Electronic Journal of Combinatorics, 19(2):#P40.
Frucht, R. and Harary, F. (1970). On the corona of two graphs.
Gonçalves, D., Parreau, A., and Pinlou, A. (2013). Locally identifying coloring in bounded expansion classes of graphs. Discrete Applied Mathematics, 161(18):2946–2951.
Martins, N. and Sampaio, R. (2018). Locally identifying coloring of graphs with few p4s. Theoretical Computer Science, 707:69–76.
Mohan, S., Geetha, J., and Somasundaram, K. (2017). Total coloring of corona product of two graphs. Australas. J Comb., 68:15–22.
Oliveira, M. R., Cappelle, R. M., and Coelho, H. (2023a). Locally identifying coloring in some chordal graphs. Matemática Contemporânea, 22:152–160.
Oliveira, R. M., Cappelle, M. R., and Coelho, H. (2023b). Coloração de identificação local em produto cartesiano. In Anais do VIII Encontro de Teoria da Computação, pages 35–39. SBC.
Yero, I. G., Kuziak, D., and Rondón Aguilar, A. (2013). Coloring, location and domination of corona graphs. Aequationes mathematicae, 86:1–21.
Esperet, L., Gravier, S., Montassier, M., Ochem, P., and Parreau, A. (2012). Locally identifying coloring of graphs. The Electronic Journal of Combinatorics, 19(2):#P40.
Frucht, R. and Harary, F. (1970). On the corona of two graphs.
Gonçalves, D., Parreau, A., and Pinlou, A. (2013). Locally identifying coloring in bounded expansion classes of graphs. Discrete Applied Mathematics, 161(18):2946–2951.
Martins, N. and Sampaio, R. (2018). Locally identifying coloring of graphs with few p4s. Theoretical Computer Science, 707:69–76.
Mohan, S., Geetha, J., and Somasundaram, K. (2017). Total coloring of corona product of two graphs. Australas. J Comb., 68:15–22.
Oliveira, M. R., Cappelle, R. M., and Coelho, H. (2023a). Locally identifying coloring in some chordal graphs. Matemática Contemporânea, 22:152–160.
Oliveira, R. M., Cappelle, M. R., and Coelho, H. (2023b). Coloração de identificação local em produto cartesiano. In Anais do VIII Encontro de Teoria da Computação, pages 35–39. SBC.
Yero, I. G., Kuziak, D., and Rondón Aguilar, A. (2013). Coloring, location and domination of corona graphs. Aequationes mathematicae, 86:1–21.
Publicado
21/07/2024
Como Citar
OLIVEIRA, Robson M.; CAPPELLE, Márcia R.; COELHO, Hebert.
Coloração de identificação local no produto corona de ciclos e caminhos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 119-123.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.3089.
