Note on the vertex-rainbow index of a graph (Q2048994)

Let \(G\) be a graph and let \(S\) be arbitrary \(k\)-subset of \(V(G)\) for some \(k\in\{2,3,\dots,|V(G)|\}\). An \(S\)-tree is any subtree of \(G\) that contains all vertices from \(S\). A vertex coloring, that is not necessarily a proper coloring, is called a \(k\)-vertex-rainbow coloring if there exists an \(S\)-tree such that all the vertices of \(V(T)-S\) have different coloring for any \(k\)-subset \(S\) of \(V(G)\). The minimum number of colors in such a coloring is then called \(k\)-vertex rainbow index and is denoted by \(rvx_k(G)\). The main result of this note is that \(rvx_3(G)>\frac{3|V(G)|}{\delta}+16\) holds for a connected graph \(G\) with minimum degree \(\delta\). On the case of cycles, the authors also show that the \(k\)-vertex rainbow index is not hereditary with respect to \(k\).