A connected edge-colored graph G is said to be rainbow-connected if any two distinct vertices of G are connected by a path whose edges have pairwise distinct colors, and the rainbow connection number rc(G) of G is the minimum number of colors that can make G rainbow-connected. We consider families F of connected graphs for which there is a constant k(F) such that every connected F-free graph G with minimum degree at least 2 satisfies rc(G) <= diam(G) k(F), where diam(G) is the diameter of G. In this paper, we give a complete answer for vertical bar F vertical bar = 1, and a partial answer for vertical bar F vertical bar = 2. (C) 2014 Elsevier B.V. All rights reserved.
展开▼
