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 \({rainbow\; path}\) if no two edges of \(G\) 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 \(\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.