Authors:
W. Li, X. Li, J. Zhang
Title:
Rainbow vertex-connection and forbidden subgraphs
Source:
Discussiones Mathematicae Graph Theory
Received 25.02.2016, Revised 21.10.2016, Accepted 21.10.2016, doi: 10.7151/dmgt.2004

Abstract:
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 \mathcal{F} of connected graphs with |\mathcal{F}|∈{1,2}, for which there is a constant k\mathcal{F} such that, for every connected \mathcal{F}-free graph G, rvc(G)≤ diam(G)+k\mathcal{F}, where diam(G) is the diameter of G.
Keywords:
vertex-rainbow path, rainbow vertex-connection, forbidden subgraphs

Links:
PDF