Rainbow connection number of dense graphs

Abstract

An edge-colored graph $G$ is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G)\le 3$, if $|E(G)|\ge \left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+2$, and $rc(G)\le 4$, if $|E(G)|\ge \left(\genfrac{}{}{0ex}{}{n-3}{2}\right)+3$. These bounds are sharp.

8 pages

References in corpus (1)

• Rainbow connections of graphs -- A survey