Some results on $3$-monochromatic vertex index

Abstract

A tree $T$ in a vertex colored graph $G$ is called a vertex-monochromatic tree if all the internal vertices of $T$ have the same color. For $S\subseteq V(G)$, a vertex-monochromatic $S$-tree in $G$ is a vertex-monochromatic tree of $G$ containing the vertices of $S$. For a connected graph $G$ and a given integer $k$ with $2\leq k\leq |V(G)|$, the $k$-monochromatic vertex-index $mvx_{k}(G)$ of $G$ is the maximum number of colors needed such that for each subset $S\subseteq V(G)$ of $k$ vertices, there exists a vertex-monochromatic $S$-tree. In this paper, we show that
$mvx_{3}(G)\leq l(G)+\delta (G)$. We present all graphs with $mvx_{3}(G)$ of $3,4$, and verify that almost all simple graphs satisfy $mvx_{3}(G)= n$. We investigate the $3$-monochromatic vertex-index of a graph $G$ of order $n$ and $\omega(G)=n-i$ for $1\leq i\leq 3$.