The rainbow connection of a graph is (at most) reciprocal to its minimum degree
✍ Scribed by Michael Krivelevich; Raphael Yuster
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 83 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
An edge‐colored graph __G__is rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make __G__rainbow edge‐connected. We prove that if __G__has __n__vertices and minimum degree δ then rc(G)<20____n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph __G__is rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make __G__rainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if __G__has __n__vertices and minimum degree δ then rvc(G)<11____n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010