A Note on the $3$-rainbow Index of Complete Bipartite Graphs

Abstract

A tree $T$, in an edge-colored graph $G$, is called a rainbow tree if no two edges of $T$ are assigned the same color. For a vertex subset $S\subseteq V(G)$, a tree that connects $S$ in $G$ is called an $S$-tree. A $k$-rainbow coloring of $G$ is an edge coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$, there exists a rainbow $S$-tree $T$ in $G$. The minimum number of colors needed in a $k$-rainbow coloring of $G$ is the $k$-rainbow index of $G$, denoted by $r{x}_k(G)$. It is NP-hard to compute the $r{x}_k(G)$ for the general graphs $G$. We consider the $3$-rainbow index of complete bipartite graphs $K_{s,t}$. For $3\le s\le t$, we have determined the tight bounds of $r{x}_3(K_{s,t})$. In this paper, we continue the study. For $2\le s\le t$, we develop a converse idea and apply it with the model of chessboard to study the problem. Finally, we obtain the exact value of $r{x}_3(K_{s,t})$ with $2\le s\le t$.