On the Equitable Vertex Arboricity of Graphs

Abstract

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu, Zhang and Li introduced the concept of equitable $(t,k)$-tree-coloring, which can be regarded as a generalization of proper equitable $t$-coloring. The \emph{strong equitable vertex $k$-arboricity} of $G$, denoted by ${v{a}_k}^{\equiv }(G)$, is the smallest integer $t$ such that $G$ has an equitable $(t^{\prime },k)$-tree-coloring for every $t^{\prime }\ge t$. The exact value of strong equitable vertex $k$-arboricity of complete equipartition bipartite graph $K_{n,n}$ was studied by Wu, Zhang and Li. In this paper, we first get a sharp upper bound of strong equitable vertex arboricity of complete bipartite graph$K_{n,n+\ell }(1\le \ell \le n)$, that is, ${v{a}_2}^{\equiv }(K_{n,n+\ell })\le 2\lfloor \frac{n+\ell +1}{3}\rfloor$. Next, we obtain a sufficient and necessary condition on an equitable $(q,\infty )$-tree coloring of a complete equipartition tripartite graph, and study the strong equitable vertex arboricity of forests. For a simple graph $G$ of order $n$, we show that $1\le {v{a}_k}^{\equiv }(G)\le \lceil n/2\rceil$. Furthermore, graphs with ${v{a}_k}^{\equiv }(G)=1,\lceil \frac{n}{2}\rceil ,\lceil \frac{n}{2}\rceil -1$ are characterized, respectively. In the end, we obtain the Nordhaus-Gaddum type results of strong equitable vertex $k$-arboricity for general $k$.

14 pages, 0 figures