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ásDO - 10.5753/erigo.2025.16987, 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.