2021/07/01 by Laomala, Janejira, Nakprasit, Keaitsuda, Nakprasit, Kittikorn +1
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.00213
An equitable (q, r)-tree-coloring of a graph G is a q-coloring of G such that the subgraph induced by each color class is a forest of maximum degree at most r and the sizes of any two color classes differ by at most 1. Let the strong equitable vertex r-arboricity of a graph G, denoted by va^≡r (G), be the minimum p such that G has an equitable (q, r)-tree-coloring for every q≥ p. The values of va^≡1 (Kn,n) were investigated by Tao and Lin and Wu, Zhang, and Li where exact values of va^≡1 (Kn,n) were found in some special cases. In this paper, we extend their results by giving the exact values of va^≡1 (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 va^≡1 (Km,n) and va^≡1 (G) where G is a balanced complete k-partite graph Kn,…,n.