Coloração de identificação local em grafos split-comparabilidade

• Robson Oliveira UFG
• Márcia Cappelle UFG
• Hebert Coelho UFG
• Julliano Nascimento UFG

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

Resumo

Uma coloração de identificação local (lid-coloração) é uma coloração própria de vértices tal que vértices adjacentes com vizinhanças fechadas distintas devem ser distinguidos pelos conjuntos de cores presentes nessas vizinhanças. O número lid-cromático χ_lid(G) de um grafo G é o menor número de cores necessário em uma lid-coloração. Neste trabalho investigamos o número lid-cromático de uma subclasse de grafos split-comparabilidade, caracterizada por uma estrutura de vizinhança mais restrita, obtendo expressões exatas para χ_lid(G) em função da estrutura do grafo e analisando o efeito da remoção de vértices gêmeos.

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.

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.

Oliveira, M. R., Cappelle, R. M., and Coelho, H. (2023). Locally identifying coloring in some chordal graphs. Matemática Contemporânea, 22:152–160.

Oliveira, R. M., Cappelle, M. R., and Coelho, H. (2024a). Coloração de identificação local no produto corona de ciclos e caminhos. In Anais do IX Encontro de Teoria da Computação, pages 119–123. SBC.

Oliveira, R. M., Cappelle, M. R., and Coelho, H. (2024b). Locally identifying coloring of corona products: Complexity and structural results. In Anais do LVI Simpósio Brasileiro de Pesquisa Operacional, pages 1–12.

Ortiz, C. and Villanueva, M. (2010). Threshold dimension of split-permutation graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 75:117.