Rainbow connection number and independence number of a graph

Abstract

Let $G$ be an edge-colored connected graph. A path of $G$ is called rainbow if its every edge is colored by a distinct color. $G$ is called rainbow connected if there exists a rainbow path between every two vertices of $G$. The minimum number of colors that are needed to make $G$ rainbow connected is called the rainbow connection number of $G$, denoted by $rc(G)$. In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if $G$ is a connected graph, then $rc(G)\le 2\alpha (G)-1$. Two examples $G$ are given to show that the upper bound $2\alpha (G)-1$ is equal to the diameter of $G$, and therefore the best possible since the diameter is a lower bound of $rc(G)$.

14 pages

References in corpus (2)

• Hardness and Algorithms for Rainbow Connection
• On a question on graphs with rainbow connection number 2