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

Abstract

Given a graph G, an edge-coloring of G is an assingment of colors to the edges of G. A proper edge-coloring is an edge coloring if adjacent edges have different colors. A rainbow coloring of a connected graph G is an edge coloring that is not necessarily proper such that there is a path between any pair of vertices of G whose edge colors are pairwise distinct. The rainbow connection number of a graph G, denoted as rc(G), is the least number of colors for which there is a rainbow coloring of G. A graph G is rainbow critical if its rainbow connection number increases when we remove any edge from G. In this work we determine the rainbow connection number for the cartesian product graphs CmxPn when mis odd and CmxCn when m and n have distinct parities. For the case in which n and m are odd, we prove that rc(CmxCn)<=(m+n)/2. We also show that the cartesian product PmxPn is rainbow critical if and only if it is a path Pn, n > 1, or a C4 and that the cartesian product Cm x Pn is not rainbow critical when m is even and n > 1.