@article{ChandranIssacLaurietal.2022,
  author    = {Chandran, Sunil L. and Issac, Davis and Lauri, Juho and van Leeuwen, Erik Jan},
  title     = {Upper bounding rainbow connection number by forest number},
  series = {Discrete mathematics},
  volume    = {345},
  journal   = {Discrete mathematics},
  number    = {7},
  publisher = {Elsevier},
  address   = {Amsterdam [u.a.]},
  issn      = {0012-365X},
  doi       = {10.1016/j.disc.2022.112829},
  pages     = {22},
  year      = {2022},
  abstract  = {A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph G is the rainbow connection number of G, denoted by rc(G).\& nbsp;A simple way to rainbow-connect a graph G is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of G. This proves that rc(G) <= |V (G)|-1. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of t(G)-1 for rc(G), where t(G) is the number of vertices in the largest induced tree of G? The answer turns out to be negative, as there are counter-examples that show that even c .t(G) is not an upper bound for rc(G) for any given constant c.\& nbsp;In this work we show that if we consider the forest number f(G), the number of vertices in a maximum induced forest of G, instead of t(G), then surprisingly we do get an upper bound. More specifically, we prove that rc(G) <= f(G) + 2. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound.},
  language  = {en}
}