Sobre Coloração de Prismas Complementares

• Luiz S. Almeida UFG
• Márcia R. Cappelle UFG
• Diane Castonguay UFG

DOI: https://doi.org/10.5753/erigo.2025.16987

Resumo

Este artigo investiga propriedades de coloração de prismas complementares GG, que são grafos formados pela combinação da cópia de um grafo G com a cópia de seu complemento G através de um emparelhamento perfeito de vértices correspondentes. Apresentamos limites superiores e inferiores para o número cromático em algumas classes de grafos. Para grafos bipartidos completos K_r,s, determinamos o valor exato de χ(K_r,sK_r,s) em função de r e s. Para ciclos C_n e caminhos P_n com n ≥ 5, estabelecemos que χ(C_nC_n) = χ(P_nP_n) = ⌈n/2⌉. Adicionalmente, apresentamos cotas inferiores para prismas complementares de grafos perfeitos e planares. Os resultados ajustam os limites de trabalhos anteriores e contribuem para o entendimento da estrutura combinatória destes grafos por meio de construções algorítmicas.

Palavras-chave: Prismas complementares, Coloração de grafos, Número cromático, Grafos bipartidos, Ciclos e caminhos

Referências

Appel, K. and Haken, W. (1978). The Four-Color Problem, pages 153–180. Springer New York, New York, NY.

Bendali-Braham, A., Ikhlef-Eschouf, N., and Blidia, M. (2019). Some results on the b-chromatic number in complementary prism graphs. RAIRO-Operations Research, 53(4):1187–1195.

Bondy, J. A. and Murty, U. (2008). Graduate texts in mathematics, volume 244. Springer.

Cappelle, M. R., Coelho, E. M., Foulds, L. R., and Longo, H. J. (2019). Open-independent, open-locating-dominating sets in complementary prism graphs. Electronic Notes in Theoretical Computer Science, 346:253–264.

Cappelle, M. R., Coelho, E. M., Foulds, L. R., and Longo, H. J. (2022). Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs. Discrete Applied Mathematics, 323:124–133.

Castonguay, D., Dias, E. S., Mesquita, F. N., and Nascimento, J. R. (2025). Computing a 3-role assignment is polynomial-time solvable on complementary prisms. International Journal of Foundations of Computer Science, pages 1–24.

Haynes, T. W., Henning, M. A., Slater, P. J., and van der Merwe, L. C. (2007). The complementary product of two graphs. Bull. Instit. Combin. Appl, 51:21–30.

Mortosa, O. S., Cappelle, M. R., and Coelho, E. (2022). K-independência em prismas complementares é NP-completo. In Encontro de Teoria da Computação (ETC), pages 133–136. SBC.

Nordhaus, E. A. and Gaddum, J. W. (1956). On complementary graphs. The American Mathematical Monthly, 63(3):175–177.

Raksha, M., Hithavarshini, P., Dominic, C., and Sudev, N. (2020). Injective coloring of complementary prism and generalized complementary prism graphs. Discrete Mathematics, Algorithms and Applications, 12(02):2050026.

Zatesko, L. M., Carmo, R., Guedes, A. L., Zorzi, A., Machado, R. C., and Figueiredo, C. M. (2019). On the chromatic index of complementary prisms. Acta Mathematica Universitatis Comenianae, 88(3):1071–1077.