Some Remarks on Rainbow Connectivity |
| |
| Authors: | Nina Kam?ev Michael Krivelevich Benny Sudakov |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS, ETH, ZURICH, SWITZERLANDContract grant sponsors: USA‐Israel BSF grant and Israel Science Foundation (to M. K.);2. contract grant sponsor: SNSF;3. contract grant number: 200021‐149111 (to B. S.).;4. SCHOOL OF MATHEMATICAL SCIENCES, RAYMOND AND BEVERLY SACKLER FACULTY OF EXACT SCIENCES, TEL AVIV UNIVERSITY, TEL AVIV, ISRAEL;5. DEPARTMENT OF MATHEMATICS, ETH, ZURICH, SWITZERLAND |
| |
| Abstract: | An edge (vertex) colored graph is rainbow‐connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones. |
| |
| Keywords: | random regular graphs diameter rainbow connectivity |
|
|
