Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950941 | Information Processing Letters | 2017 | 5 Pages |
â¢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).