Coloração arco-íris em grafos resultantes de produto cartesiano

• Aleffer Rocha
• Sheila Morais Almeida

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

Resumo

O número de conexão arco-íris de um grafo conexo G, denotado por rc(G), é o menor número de cores necessárias para colorir as arestas de G, de forma que entre qualquer par de vértices exista um caminho cujas cores das arestas são duas a duas distintas. Neste trabalho determinamos o número de conexão arco-íris para os grafos Cm Pn quando m é ímpar e Cm Cn quando m e n têm paridades distintas. Para os casos em que m e n são ímpares, provamos que rc(Cm Cn) m2+n .