Discussiones Mathematicae Graph Theory 33(1) (2013) 181-192
doi: 10.7151/dmgt.1640

Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday

[BIBTex] [PDF] [PS]

Rainbow Connection in Sparse Graphs

Arnfried Kemnitz

Computational Mathematics, Technische Universität Braunschweig
38 023 Braunschweig, Germany

Jakub Przybyło and Mariusz Wożniak

AGH University of Science and Technology
al. A. Mickiewicza 30, 30-059 Kraków, Poland

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
Technische Universität Bergakademie Freiberg
09 596 Freiberg, Germany


An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, G is rainbow-connected. In this paper we prove that denoted by rc(G), is the minimum number of colours such that rc(G) ≤ k if |V(G) | = n and |E(G) | ≥ ((n −k+1) || 2) + k −1 for all integers n and k with n −6 ≤ k ≤ n −3. We also show that this bound is tight.

Keywords: rainbow-connected graph, rainbow colouring, rainbow connection number

2010 Mathematics Subject Classification: 05C15.


[1]J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
[2]Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #57.
[3]S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011) 330--347, doi: 10.1007/s10878-009-9250-9.
[4]L.S. Chandran, A. Das, D. Rajendraprasad, and N.M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory 71 (2012) 206--218, doi: 10.1002/jgt.20643.
[5]G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohemica 133 (2008) 85--98.
[6]A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24--28.
[7]J. Ekstein, P. Holub, T. Kaiser, M. Koch, S. Matos Camacho, Z. Ryjáček and I. Schiermeyer, The rainbow connection number in 2-connected graphs, Discrete Math, doi: 10.1016/j.disc.2012.04.022.
[8]E. Györi, On division of graphs to connected subgraphs, Combinatorics, Vol. I, pp. 485--494, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam, 1978.
[9]A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313--320, doi: 10.7151/dmgt.1547.
[10]M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185--191.
[11]V.B. Le and Zs. Tuza, Finding optimal rainbow connection is hard, Preprint 2009.
[12]X. Li, M. Liu, and I. Schiermeyer, Rainbow connection number of dense graphs, to appear in Discuss. Math. Graph Theory.
arXiv: 1110.5772v1 [math.CO] 2011.
[13]X. Li and Y. Sun, Rainbow Connections of Graphs, Springer Briefs in Math., Springer, New York, 2012.
[14]L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Hungar. 30 (1977) 241--251, doi: 10.1007/BF01896190.
[15]I. Schiermeyer, Rainbow connection in graphs with minimum degree three, Lecture Notes Computer Science 5874 (2009) 432--437, doi: 10.1007/978-3-642-10217-2_42.

Received 11 April 2012
Revised 11 July 2012
Accepted 11 July 2012