Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2

A connected edge-colored graph GG is rainbow-connected if any two distinct vertices of GG are connected by a path whose edges have pairwise distinct colors; the rainbow connection number rc(G) of GG is the minimum number of colors that are needed in order to make GG rainbow connected. In this paper, we complete the discussion of pairs (X,Y)(X,Y) of connected graphs for which there is a constant kXYkXY such that, for every connected (X,Y)(X,Y)-free graph GG with minimum degree at least 2, rc(G)≤diam(G)+kXY (where diam(G) is the diameter of GG), by giving a complete characterization. In particular, we show that for every connected (Z3,S3,3,3)(Z3,S3,3,3)-free graph GG with δ(G)≥2δ(G)≥2, rc(G)≤diam(G)+156, and, for every connected (S2,2,2,N2,2,2)(S2,2,2,N2,2,2)-free graph GG with δ(G)≥2δ(G)≥2, rc(G)≤diam(G)+72.