Geodesic
Rainbow Vertex-Connection and Forbidden Subgraphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 143-154

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

A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ 1, 2, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
Keywords: vertex-rainbow path, rainbow vertex-connection, forbidden sub-graphs 
@article{DMGT_2018_38_1_a11,
     author = {Li, Wenjing and Li, Xueliang and Zhang, Jingshu},
     title = {Rainbow {Vertex-Connection} and {Forbidden} {Subgraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {143--154},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a11/}
}
TY  - JOUR
AU  - Li, Wenjing
AU  - Li, Xueliang
AU  - Zhang, Jingshu
TI  - Rainbow Vertex-Connection and Forbidden Subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 143
EP  - 154
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a11/
LA  - en
ID  - DMGT_2018_38_1_a11
ER  - 
%0 Journal Article
%A Li, Wenjing
%A Li, Xueliang
%A Zhang, Jingshu
%T Rainbow Vertex-Connection and Forbidden Subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 143-154
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a11/
%G en
%F DMGT_2018_38_1_a11
Li, Wenjing; Li, Xueliang; Zhang, Jingshu. Rainbow Vertex-Connection and Forbidden Subgraphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 143-154. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a11/