Coloração de identificação local em produto Cartesiano

• Robson M. Oliveira UFG
• Márcia R. Cappelle UFG
• Hebert Coelho UFG

DOI: https://doi.org/10.5753/etc.2023.230766

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 para o produto Cartesiano K_m□P_n e limites inferiores e superiores para o lidcromático de K_m□C_n e K_m□K_n.

Referências

Bhyravarapu, S., Kumari, S., and Reddy, I. (2023). On locally identifying coloring of graphs. In Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings, pages 147–158. Springer.

Esperet, L., Gravier, S., Montassier, M., Ochem, P., and Parreau, A. (2010). Locally identifying coloring of graphs. arXiv preprint arXiv:1010.5624.

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.

Oliveira, M., Cappelle, R. M., and Coelho, H. Locally identifying coloring in some chordal graphs. Submetido.