
arXiv: 1602.00922
A path in a vertex-colored graph is called \emph{vertex-rainbow} if its internal vertices have pairwise distinct colors. A graph $G$ is \emph{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 \emph{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}|\in\{1,2\}$, for which there is a constant $k_\mathcal{F}$ such that, for every connected $\mathcal{F}$-free graph $G$, $rvc(G)\leq diam(G)+k_\mathcal{F}$, where $diam(G)$ is the diameter of $G$.
11 pages
Extremal problems in graph theory, Connectivity, forbidden sub-graphs, 05C15, 05C35, 05C38, 05C40, Coloring of graphs and hypergraphs, vertex-rainbow path, 05c15, 05c38, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05c35, rainbow vertex-connection, 05c40, Paths and cycles, Mathematics
Extremal problems in graph theory, Connectivity, forbidden sub-graphs, 05C15, 05C35, 05C38, 05C40, Coloring of graphs and hypergraphs, vertex-rainbow path, 05c15, 05c38, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05c35, rainbow vertex-connection, 05c40, Paths and cycles, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
