Coloracão arco-íris em classes de grafos

Abstract

Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph 𝐺, denoted 𝑟𝑐(𝐺), is the least 𝑘 for which 𝐺 admits a (not necessarily proper) 𝑘-edge-coloring such that between any pair of vertices there is a rainbow path, i. e., a path whose edge colors are all distinct. Given an edge coloring 𝜑 for a graph 𝐺, if between any pair of vertices there is a minimum path which is rainbow, then 𝜑 is a strong rainbow coloring. The minimum number of colors for which a given graph 𝐺 has a strong rainbow coloring is the strong rainbow connection number of 𝐺. A graph 𝐺 is rainbow critical if the deletion of any edge of 𝐺 increases 𝑟𝑐(𝐺). In this work, we determine the rainbow connection number and the strong rainbow connection number of shadow graphs of paths, triple triangular snake graphs, circulant graphs 𝐶 1,𝑘 2𝑘 and join graphs 𝐺 + 𝐾𝑚 when 𝐺 has 𝑟𝑐(𝐺) ≤ 2. We also determine the rainbow connection number of join graphs of sunlet (𝑅𝑛) with 𝐺 when |𝑉 (𝐺)| ≥ 𝑛 − 1 and of cographs with three pendent vertices. We found new upper bounds for the rainbow connection number of snake graphs, join graphs of two graphs with universal vertices, and join graphs 𝑅𝑛 + 𝐾𝑚 when 𝑚 ≤ 𝑛 − 2. We also present necessary and sufficient conditions for the criticality of fan graphs, Cartesian products 𝐺 × 𝑃𝑛 when 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 2 or when 𝐺 is a pan graph, 𝐺 × 𝐾𝑚 when 𝑟𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) ≥ 1, and 𝐶𝑚 × 𝐶𝑛 when 𝑚 and 𝑛 are even.