2015/05/30 by Yaping Mao, Mao, Yaping, Zhiwei Guo +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1506.00132
openalex publication_date 2015/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu, Zhang and Li introduced the concept of equitable (t,k)-tree-coloring, which can be regarded as a generalization of proper equitable t-coloring. The strong equitable vertex k-arboricity of G, denoted by vak^≡(G), is the smallest integer t such that G has an equitable (t', k)-tree-coloring for every t'≥ t. The exact value of strong equitable vertex k-arboricity of complete equipartition bipartite graph Kn,n was studied by Wu, Zhang and Li. In this paper, we first get a sharp upper bound of strong equitable vertex arboricity of complete bipartite graphKn,n+ℓ (1≤ ℓ≤ n), that is, va2^≡(Kn,n+ℓ)≤2\lfloor(n+ℓ+1)/(3)\rfloor. Next, we obtain a sufficient and necessary condition on an equitable (q,∞)-tree coloring of a complete equipartition tripartite graph, and study the strong equitable vertex arboricity of forests. For a simple graph G of order n, we show that 1≤ vak^≡(G)≤ \lceil n/2 \rceil. Furthermore, graphs with vak^≡(G)=1,\lceil(n)/(2)\rceil,\lceil(n)/(2)\rceil-1 are characterized, respectively. In the end, we obtain the Nordhaus-Gaddum type results of strong equitable vertex k-arboricity for general k.