The Strong Equitable Vertex 1-Arboricity of Complete Bipartite Graphs and Balanced Complete k-Partite Graphs

An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color classes differ by at most one. An equitable (q,r)-tree-coloring of a graph G is an equitable q-coloring of G such that the subgraph induced by each color class is a forest of maximum degree at most r. Let the strong equitable vertex r-arboricity of a graph G, denoted by var & EQUIV;(G), be the minimum p such that G has an equitable (q,r)-tree-coloring for every q & GE;p. The values of va1 & EQUIV;(Kn,n) were investigated by Tao and Lin and Wu, Zhang, and Li where exact values of va1 & EQUIV;(Kn,n) were found in some special cases. In this paper, we extend their results by giving the exact values of va1 & EQUIV;(Kn,n) for all cases. In the process, we introduce a new function related to an equitable coloring and obtain a more general result by determining the exact value of each va1 & EQUIV;(Km,n) and va1 & EQUIV;(G) where G is a balanced complete k-partite graph Kn, horizontal ellipsis ,n. Both complete bipartite graphs Km,n and balanced complete k-partite graphs Kn, horizontal ellipsis ,n are symmetry in several aspects and also studied broadly. For the other aspect of symmetry, by the definition of equitable k-coloring of graphs, in a specific case that the number of colors divides the number of vertices of graph, we can say that the graph is a balanced k-partite graph.

Automated summary

This paper investigates the concepts of equitable coloring and tree coloring of graphs, introduces the notion of strong equitable vertex arboricity, and provides results for complete bipartite graphs and balanced complete k-partite graphs.