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: |