Geodesic
Rainbow connection number and connectivity
The electronic journal of combinatorics, Tome 19 (2012) no. 1

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv
The rainbow connection number, $rc(G)$, of a connected graph $G$ is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that $rc(G)\leq \lceil\frac{n}{2}\rceil$ for any 2-connected graph with at least three vertices. We conjecture that $rc(G)\leq n/\kappa+C$ for a $\kappa$-connected graph $G$ of order $n$, where $C$ is a constant, and prove the conjecture for certain classes of graphs. We also prove that $rc(G)\leq(2+\varepsilon)n/\kappa+23/\varepsilon^2$ for any $\varepsilon>0$.
DOI : 10.37236/1172
Classification : 05C40, 05C15
Mots-clés : rainbow coloring, rainbow connection number, connectivity, 2-connected graph, ear decomposition, chordal graph, girth 
Xueliang Li; Sujuan Liu; L. Sunil Chandran; Rogers Mathew; Deepak Rajendraprasad. Rainbow connection number and connectivity. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/1172
@article{10_37236_1172,
     author = {Xueliang Li and Sujuan Liu and L. Sunil Chandran and Rogers Mathew and Deepak Rajendraprasad},
     title = {Rainbow connection number and connectivity},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {1},
     doi = {10.37236/1172},
     zbl = {1243.05133},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1172/}
}
TY  - JOUR
AU  - Xueliang Li
AU  - Sujuan Liu
AU  - L. Sunil Chandran
AU  - Rogers Mathew
AU  - Deepak Rajendraprasad
TI  - Rainbow connection number and connectivity
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1172/
DO  - 10.37236/1172
ID  - 10_37236_1172
ER  - 
%0 Journal Article
%A Xueliang Li
%A Sujuan Liu
%A L. Sunil Chandran
%A Rogers Mathew
%A Deepak Rajendraprasad
%T Rainbow connection number and connectivity
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1172/
%R 10.37236/1172
%F 10_37236_1172

Cité par Sources :