Equitable vertex arboricity of graphs

Abstract

An equitable $(t,k,d)$-tree-coloring of a graph $G$ is a coloring to vertices of $G$ such that the sizes of any two color classes differ by at most one and the subgraph induced by each color class is a forest of maximum degree at most $k$ and diameter at most $d$. The minimum $t$ such that $G$ has an equitable $(t^{\prime },k,d)$-tree-coloring for every $t^{\prime }\ge t$ is called the strong equitable $(k,d)$-vertex-arboricity and denoted by $v{a}_{k,d}^{\equiv }(G)$. In this paper, we give sharp upper bounds for $v{a}_{1,1}^{\equiv }(K_{n,n})$ and $v{a}_{k,\infty }^{\equiv }(K_{n,n})$ by showing that $v{a}_{1,1}^{\equiv }(K_{n,n})=O(n)$ and $va^{\equiv}_{k,\infty}(K_{n,n})=O(n^{\1/2})$ for every $k\ge 2$. It is also proved that $v{a}_{\infty ,\infty }^{\equiv }(G)\le 3$ for every planar graph $G$ with girth at least 5 and $v{a}_{\infty ,\infty }^{\equiv }(G)\le 2$ for every planar graph $G$ with girth at least 6 and for every outerplanar graph. We conjecture that $v{a}_{\infty ,\infty }^{\equiv }(G)=O(1)$ for every planar graph and $v{a}_{\infty ,\infty }^{\equiv }(G)\le \lceil \frac{\Delta (G)+1}{2}\rceil$ for every graph $G$.