Geodesic
Rainbow connection number and connectivity
The electronic journal of combinatorics, Tome 19 (2012) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :