Upper bounds for the rainbow connection numbers of line graphs

Abstract

A path in an edge-colored graph $G$, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if for any two vertices of $G$ there is a rainbow path connecting them. The rainbow connection number of $G$, denoted by $rc(G)$, is defined as the smallest number of colors by using which there is a coloring such that $G$ is rainbow connected. In this paper, we mainly study the rainbow connection number of the line graph of a graph which contains triangles and get two sharp upper bounds for $rc(L(G))$, in terms of the number of edge-disjoint triangles of $G$ where $L(G)$ is the line graph of $G$. We also give results on the iterated line graphs.

arXiv comment11 pages