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/

[1] G. Bacsó and Zs. Tuza, Dominating cliques in P5-free graphs, Period. Math. Hungar. 21 (1990) 303–308. doi:10.1007/BF02352694

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer-Verlag, London, 2008).

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

[4] L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412 (2011) 4531–4535. doi:10.1016/j.tcs.2011.04.032

[5] P. Holub, Z. Ryjáček, I. Schiermeyer and P. Vrána, Rainbow connection and foridden subgraphs, Discrete Math. 338 (2015) 1706–1713. doi:10.1016/j.disc.2014.08.008

[6] 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. doi:10.1002/jgt.20418

[7] S. Li, X. Li and Y. Shi, Note on the complexity of decidining the rainbow ( vertex- ) connectedness for bipartite graphs, Appl. Math. Comput. 258 (2015) 155–161. doi:10.1016/j.amc.2015.02.015

[8] X. Li and S. Liu, Tight upper bound of the rainbow vertex-connection number for 2- connected graphs, Discrete Appl. Math. 173 (2014) 62–69. doi:10.1016/j.dam.2014.04.002

[9] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307–313. doi:10.7151/dmgt.1664

[10] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[11] X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer-Verlag, New York, 2012).