Sobre Coloração de Prismas Complementares - Almeida, Luiz S.; Cappelle, Márcia R.; Castonguay, Diane (Anais da Escola Regional de Informática de Goiás (ERI-GO); 2025: Anais da XIII Escola Regional de Informática de Goiás, 2025)
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,s K r,s ) em função de r e s. Para ciclos C n e caminhos P n com n ≥ 5, estabelecemos que χ(C n C n ) = χ(P n P 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.