Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six (Q2337023)

Summary: A \textit{rainbow\(t\)-coloring} of a \(t\)-connected graph \(G\) is an edge coloring such that for any two distinct vertices \(u\) and \(v\) of \(G\) there are at least \(t\) internally vertex-disjoint rainbow \((u, v)\)-paths. In this work, we apply a Rank Genetic Algorithm to search for rainbow \(t\)-colorings of the family of Moore cages with girth six \((t; 6)\)-cages. We found that an upper bound in the number of colors needed to produce a rainbow 4-coloring of a \((4; 6)\)-cage is 7, improving the one currently known, which is 13. The computation of the minimum number of colors of a rainbow coloring is known to be NP-Hard and the Rank Genetic Algorithm showed good behavior finding rainbow \(t\)-colorings with a small number of colors.