| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4647451 | Discrete Mathematics | 2013 | 9 Pages |
Abstract
The rainbow connection number of a graph GG is the least number of colours in a (not necessarily proper) edge-colouring of GG such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with nn vertices is at most ⌈n/2⌉⌈n/2⌉. The bound is optimal.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jan Ekstein, Přemysl Holub, Tomáš Kaiser, Maria Koch, Stephan Matos Camacho, Zdeněk Ryjáček, Ingo Schiermeyer,