Geodesic
Vertex rainbow colorings of graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 63-80 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number vrc(G) of G. Thus if G is a connected graph of order n ≥ 2, then 2 ≤ vrc(G) ≤ n. We present characterizations of all connected graphs G of order n for which vrc(G) ∈ 2,n-1,n and study the relationship between vrc(G) and the chromatic number χ(G) of G. For a connected graph G of order n and size m, the number m-n+1 is the cycle rank of G. Vertex rainbow connection numbers are determined for all connected graphs of cycle rank 0 or 1 and these numbers are investigated for connected graphs of cycle rank 2.
Keywords: rainbow path, vertex rainbow coloring, vertex rainbow connection number 
@article{DMGT_2012_32_1_a5,
     author = {Fujie-Okamoto, Futaba and Kolasinski, Kyle and Lin, Jianwei and Zhang, Ping},
     title = {Vertex rainbow colorings of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {63--80},
     year = {2012},
     volume = {32},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a5/}
}
TY  - JOUR
AU  - Fujie-Okamoto, Futaba
AU  - Kolasinski, Kyle
AU  - Lin, Jianwei
AU  - Zhang, Ping
TI  - Vertex rainbow colorings of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 63
EP  - 80
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a5/
LA  - en
ID  - DMGT_2012_32_1_a5
ER  - 
%0 Journal Article
%A Fujie-Okamoto, Futaba
%A Kolasinski, Kyle
%A Lin, Jianwei
%A Zhang, Ping
%T Vertex rainbow colorings of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 63-80
%V 32
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a5/
%G en
%F DMGT_2012_32_1_a5
Fujie-Okamoto, Futaba; Kolasinski, Kyle; Lin, Jianwei; Zhang, Ping. Vertex rainbow colorings of graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 63-80. http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a5/

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

[2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81, doi: 10.1002/net.20296.

[3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367.

[4] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman Hall/CRC Press, 2009).

[5] 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

[6] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168, doi: 10.2307/2371086.