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.
@article{bwmeta1.element.doi-10_7151_dmgt_2004,
author = {Wenjing Li and Xueliang Li and Jingshu Zhang},
title = {Rainbow Vertex-Connection and Forbidden Subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {38},
year = {2018},
pages = {143-154},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_2004}
}
Wenjing Li; Xueliang Li; Jingshu Zhang. Rainbow Vertex-Connection and Forbidden Subgraphs. Discussiones Mathematicae Graph Theory, Tome 38 (2018) pp. 143-154. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_2004/