A connected edge-colored graph G is rainbow-connected if any two distinct vertices of G are connected by a path whose edges have pairwise distinct colors; the rainbow connection number rc ( G ) of G is the minimum number of colors that are needed in order to make G rainbow connected. In this paper, we complete the discussion of pairs ( X , Y ) of connected graphs for which there is a constant k X Y such that, for every connected ( X , Y ) -free graph G with minimum degree at least 2, rc ( G ) ? diam ( G ) + k X Y (where diam ( G ) is the diameter of G ), by giving a complete characterization. In particular, we show that for every connected ( Z 3 , S 3 , 3 , 3 ) -free graph G with ? ( G ) ? 2 , rc ( G ) ? diam ( G ) + 156 , and, for every connected ( S 2 , 2 , 2 , N 2 , 2 , 2 ) -free graph G with ? ( G ) ? 2 , rc ( G ) ? diam ( G ) + 72 .
['Přemysl Holub', 'Zdeněk Ryjáček', 'Ingo Schiermeyer', 'Petr Vrána']
Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2