Rainbow Connection Numbers of Line Graphs

Abstract

A path in an edge-coloring graph $G$, where adjacent edges may be colored the same, is called a $rainbowpath$ if no two edges of $G$ are colored the same. A nontrivial connected graph $G$ is $rainbowconnected$ if for any two vertices of $G$ there is a rainbow path connecting them. The $rainbowconnectionnumber$ of $G$, denoted $\text{rc}(G)$, is defined as the minimum number of colors by using which there is coloring such that $G$ is rainbow connected. In this paper, we study the rainbow connection numbers of line graphs of triangle-free graphs, and particularly, of $2$-connected triangle-free graphs according to their ear decompositions.