The strong equitable vertex 2-arboricity of complete bipartite and tripartite graphs

- Equitable vertex arboricity has many applications such as scheduling and resource allocation.
- Z. Guo, H. Zhao, Y. Mao [4] found the exact values of equitable vertex 2-arboricity of Kn,n,n except when n is divisible by 20.
- We find a linear-time algorithm to find the exact values of equitable vertex 2-arboricity for all Km,n and Kl,m,n.

A (q,r)-tree-coloring of a graph G is a q-coloring of vertices of G such that the subgraph induced by each color class is a forest of maximum degree at most r. An equitable (q,r)-tree-coloring of a graph G is a (q,r)-tree-coloring such that the sizes of any two color classes differ by at most one. Let the strong equitable vertex r-arboricity of G, denoted by var≡(G), be the minimum p such that G has an equitable (q,r)-tree-coloring for every q≥p.Z. Guo, H. Zhao, Y. Mao [4] found the exact values of va2≡(Kn,n,n) for each n except when n is divisible by 20. In this paper, we find the exact value for each va2≡(Km,n) and va2≡(Kl,m,n).