On the Equitable Vertex Arboricity of Graphs

MaRDI QIDQ6262247zbMATH OpenFDO

Authors Yaping Mao, Zhiwei Guo, Hong-Jian Lai, Haixing Zhao

Publication date 30 May 2015

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}^{e}quiv(G)$, is the smallest integer $t$ such that $G$ has an equitable $(t^{\prime },k)$-tree-coloring for every $t^{\prime }geqt$. 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}(1leqellleqn)$, that is, ${v{a}_2}^{e}quiv(K_{n,n+ell})leq2leftlfloorfracn+ell+13ightfloor$. 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 $1leq{v{a}_k}^{e}quiv(G)leqlceiln/2ceil$. Furthermore, graphs with ${v{a}_k}^{e}quiv(G)=1,lceilfracn2ceil,lceilfracn2ceil-1$ are characterized, respectively. In the end, we obtain the Nordhaus-Gaddum type results of strong equitable vertex $k$-arboricity for general $k$.

This page was built for publication: On the Equitable Vertex Arboricity of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6262247)