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

Voir la notice de l'article dans European Digital Mathematics Library

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)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.
Classification : 05C15, 05C40
Mots-clés : edge-colored graph, rainbow coloring, rainbow connection number 
@article{DMGT_2013__33_3_267532,
     author = {Xueliang Li and Mengmeng Liu and Ingo Schiermeyer},
     title = {Rainbow {Connection} {Number} of {Dense} {Graphs}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {603},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     zbl = {1275.05022},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267532/}
}
TY  - JOUR
AU  - Xueliang Li
AU  - Mengmeng Liu
AU  - Ingo Schiermeyer
TI  - Rainbow Connection Number of Dense Graphs
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 603
VL  - 33
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267532/
LA  - en
ID  - DMGT_2013__33_3_267532
ER  - 
%0 Journal Article
%A Xueliang Li
%A Mengmeng Liu
%A Ingo Schiermeyer
%T Rainbow Connection Number of Dense Graphs
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 603
%V 33
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267532/
%G en
%F DMGT_2013__33_3_267532
Xueliang Li; Mengmeng Liu; Ingo Schiermeyer. Rainbow Connection Number of Dense Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 603. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_267532/