A tree in an edge-colored connected graph G is called a rainbow tree if no two edges of it are assigned the same color. For a vertex subset \(S\subseteq V(G)\), a tree is called an S-tree if it connects S in G. A k-rainbow coloring of G is an edge-coloring of G having the property that for every set S of k vertices of G, there exists a rainbow S-tree in G. The minimum number of colors that are needed in a k-rainbow coloring of G is the k-rainbow index of G, denoted by \({\mathrm {rx}}_k(G)\). The Steiner distanced(S) of a set S of vertices of G is the minimum size of an S-tree T. The k-Steiner diameter\({\mathrm {sdiam}}_k(G)\) of G is defined as the maximum Steiner distance of S among all sets S with k vertices of G. In this paper, we focus on the 3-rainbow index of graphs and find all finite families \(\mathcal {F}\) of connected graphs, for which there is a constant \(C_\mathcal {F}\) such that, for every connected \(\mathcal {F}\)-free graph G, \({\mathrm {rx}}_3(G)\le {\mathrm {sdiam}}_3(G)+C_\mathcal {F}\).
['Wenjing Li', 'Xueliang Li', 'Jingshu Zhang']
3-Rainbow Index and Forbidden Subgraphs