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

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

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 Km□Pn e limites inferiores e superiores para o lidcromático de Km□Cn e Km□Kn.

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.
Publicado
06/08/2023
OLIVEIRA, Robson M.; CAPPELLE, Márcia R.; COELHO, Hebert. Coloração de identificação local em produto Cartesiano. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 35-39. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230766.