Some Topics On Strong Equitable Vertex Arboricity Of Graphs

The equitable coloring problem, introduced by Meyer [36] in 1973, has received considerable attention and research. We call f a t-coloring of a graph G if f is a mapping from V(G) to{1,2,..., t}. Let Vi={v|f(v)= i}. A t-coloring f of a graph G is said to be equitable if||Vi|-|Vj||≤ 1 for all i and j. Recently, Wu et al. [42] introduced the concept of equitable (t, k)-tree-coloring, which can be viewed as a generalization of proper equitable t-coloring. A (t, k)-tree-coloring is a t-coloring f of a graph G such that each component of G[Vi] is a tree of maximum degree at most k. An equitable (t, k)-tree-coloring is a (t, k)-tree-coloring that is equitable. The equitable vertex k-arboricity of a graph G, denoted by vak= (G), is the smallest integer t such that G has an equitable (t,k)-tree-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. Wu et al. [42] investigated the strong equitable vertex k-arboricity of complete equipartition bipartite graphs. They gave the upper bounds for va1≡-(Kn,n) and v∞(Kn,n), and proved that va1≡(Kn,n) for n≡ 2 (mod 3) attains the upper bound. Tao et al. [40] investigated the strong equitable vertex 1-arboricity of a balanced complete bipartite graph Kn,n for n≡ 0,1 (mod 3). They improved the upper bound and determined the exact values for some special cases. In this paper, we further investigate the strong equitable vertex arboricity of graphs. The main results of this paper are included as follows.1. Study the strong equitable vertex 1-arboricity of complete non-equipartition bipartite graph Kn,n+1 and the strong equitable vertex 2-arboricity of complete non-equipartition bipartite graph Kn,n+e (1≤e≤n). Firstly, the upper bound of va1≡ (Kn,n+1) (n≥ 1) is obtained. Next, we discuss all cases of n≡ 0,1,2 (mod 3), respectively. For n≡ 1 (mod 3), it is showed that va1≡(Kn,n+1) attains the upper bound exactly. For n= 0,2 (mod 3), let n= 3k+i (i= 0,2), we improve the upper bounds by four subcases of k≡ 0,1,2,3 (mod 4), respectively. Last, we obtain the sharp upper bound of va2≡(Kn,n+e) (1≤e≤n, and show that va2≡(Kn,n+1) exactly attains the upper bound for n = 3t (t≤ 2).2. Study the strong equitable vertex 2-arboricity of complete tripartite graph Kn,n,n and the strong equitable vertex 3-arboricity of complete tripartite graph Kn,n,n· For the strong equitable vertex 2-arboricity of Kn,n,n we obtain the exact values of va2≡(K,n,n,n) for n≡1,2,3 (mod 4), respectively. For n = 0 (mod 4), let n = 4k, the exact values of va2≡(Kn,n,n) are obtained for cases of k≡1,2,3,4 (mod 5), respectively. We give the upper bound of va2≡(Kn,n,n) for k ≡ 0 (mod 5). For the strong equitable vertex 3-arboricity of Kn,n,n, the upper bound of va3≡ (Kn,n,n) is obtained firstly. Next, we discuss all cases of n ≡ 0, 1, 2, 3 (mod 4). respectively. For n ≡ 0 (mod 4), let n = 4k, we obtain the exact values of va3≡(Kn,n,n) for k≡1,2, 3, 4 (mod 5), respectively. We improve the upper bound of va3≡(Kn,n,n) for k = 0 (mod 5). For n = 1 (mod 4), let n = 4k + 1, we obtain the exact values of va3≡(Kn,n,n) for k ≡ 2, 3, 4, 0(mod 5), respectively. We improve the upper bound of va3≡(Kn,n,n) for k≡1 (mod 5). For n≡2 (mod 4), let n = 4k + 2, we obtain the exact values of va3≡(Kn,n,n) for k≡3, 4, 0, 1 (mod 5), respectively. We improve the upper bound of va3≡(Kn,n,n) for k ≡ 2 (mod 5). For n≡ 3 (mod 4), the sharp upper bound of va3≡ (Kn,n,n) is obtained.3. Study the strong equitable vertex k-arboricity of general graphs. For general graphs, the bounds for the strong equitable vertex k-arboricity of simple graphs of order n are given, as 1≤vak≡(G) ≤[n/2]. Furthermore, graphs with vak≡(G) = 1, vak≡(G) = [n/2] and vak≡(G) = [n/2] - 1 are characterized, respectively. At the same time, we also obtain the Nordhaus-Gaddum type results of strong equitable vertex k-arboricity of general graphs.4. Study the Cartesian product with respect to the strong equitable vertex k-arboricity. At the same time, we also study strong equitable vertex k-arboricity of Cayley graphs on Abelian groups with degree 3. Firstly, we discuss the strong equi-table vertex k-arboricity of Cn, Pn and Petersen H P3. Next, for general graphs G and H, The bounds for the strong equitable vertex k-arboricity of G□H is obtained. Sub-sequently, we discuss the strong equitable vertex k-arboricity of Pn□Pm (m ≥ n≥ 2), Cn□Cm (m≥n≥3), Kn□Km(m, n≥3), hyper Petersen H P4, respectively. Last, we obtain the exact values of the strong equitable vertex k-arboricity of Cayley graphs on Abelian groups with degree 3.