Geodesic
Rainbow Connection Number of Dense Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 603-611.

Voir la notice de l'article provenant de la source Library of Science

An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥n-22 + 2, and rc(G) ≤ 4 if |E(G)| ≥n-32 + 3. These bounds are sharp.
Keywords: edge-colored graph, rainbow coloring, rainbow connection number 
@article{DMGT_2013_33_3_a9,
     author = {Li, Xueliang and Liu, Mengmeng and Schiermeyer, Ingo},
     title = {Rainbow {Connection} {Number} of {Dense} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {603--611},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a9/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Liu, Mengmeng
AU  - Schiermeyer, Ingo
TI  - Rainbow Connection Number of Dense Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 603
EP  - 611
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a9/
LA  - en
ID  - DMGT_2013_33_3_a9
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Liu, Mengmeng
%A Schiermeyer, Ingo
%T Rainbow Connection Number of Dense Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 603-611
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a9/
%G en
%F DMGT_2013_33_3_a9
Li, Xueliang; Liu, Mengmeng; Schiermeyer, Ingo. Rainbow Connection Number of Dense Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 603-611. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a9/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).

[2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98.

[3] A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24-28.

[4] A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Disscuss. Math. Graph Theory 31 (2011) 313-320. doi:10.7151/dmgt.1547

[5] X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer, New York, 2012). doi:10.1007/978-1-4614-3119-0