On various (strong) rainbow connection numbers of graphs

NEW

Problem: For finite simple connected undirected graphs, does there exist an infinite family $\mathcal F$ and a constant $K$ such that $\operatorname{src}(G)\le K$ for all $G\in\mathcal F$, but $\operatorname{srvc}(G)$ is unbounded on $\mathcal F$? Here $\operatorname{src}$ is the minimum number of edge-colors making every vertex-pair joined by a rainbow geodesic, and $\operatorname{srvc}$ is the analogous vertex-coloring parameter, where only internal vertices of a path must have distinct colors.

Result: Yes.

For $n\ge2$, construct $G_n$. Let

Let $m=\binom n2$, $r=\max(1,\lceil \log_2 m\rceil)$, and take two hub sets

Make $C,P,Q$ cliques. Join every $p_t$ to every vertex of $A$, every $q_t$ to every vertex of $B$, join $a_{ij}$ only to $c_i$ in $C$, and join $b_{ij}$ only to $c_j$ in $C$. There are no other edges.

Choose injective binary codes $\alpha:A\to\{0,1\}^r$, $\beta:B\to\{0,1\}^r$. Edge-color $G_n$ by:

and color clique edges inside $P,Q$ arbitrarily using color $1$. This uses at most $7$ colors.

For distinct $a,a'\in A$, some coordinate $t$ satisfies $\alpha(a)_t\ne\alpha(a')_t$, so $a p_t a'$ is a rainbow geodesic. Similarly for two vertices of $B$. All other type-pairs have evident shortest paths using color sequences among

or, in boundary cases, $(4/5,1,2,3)$, $(6/7,3,2,1)$, and between $P,Q$, $(4/5,1,3,6/7)$ if $n\ge3$, or $(4/5,1,2,3,6/7)$ if $n=2$. Each listed sequence is rainbow and forced by the missing inter-type edges, hence geodesic. Thus

for all $n$.

Now consider any strong rainbow vertex-coloring of $G_n$. For each $1\le i<j\le n$, the vertices $a_{ij}$ and $b_{ij}$ have a unique geodesic:

Indeed $N(a_{ij})=P\cup\{c_i\}$, $N(b_{ij})=Q\cup\{c_j\}$, and the only edge between these two neighborhoods is $c_ic_j$. Therefore $c_i$ and $c_j$ must receive distinct vertex-colors. Since this holds for every $i<j$, the vertices $c_1,\dots,c_n$ require $n$ distinct colors. Hence

Thus $\{G_n:n\ge2\}$ is an infinite family with bounded $\operatorname{src}$ and unbounded $\operatorname{srvc}$.

Citation: Problem source: Lin Chen, Xueliang Li, Henry Liu, Jinfeng Liu, “On various (strong) rainbow connection numbers of graphs,” arXiv:1601.01063, Problem 4.1. The construction above is self-contained.