| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420011 | Discrete Applied Mathematics | 2013 | 4 Pages |
Abstract
An edge-coloured graph GG is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph GG, denoted rc(G)rc(G), is the smallest number of colours that are needed in order to make GG rainbow connected. Krivelevich and Yuster (2010) [5] have shown that a connected graph GG with nn vertices has rc(G)<20nδ(G). In this paper we prove that a connected graph GG with nn vertices has rc(G)<4nδ(G)+1+4.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ingo Schiermeyer,