Vertex Arboricity Of Square Graphs

All graphs considered in this paper are finite, looless, and without multiple edges. For a graph G, let V(G), E(G), |G|, Δ(G), and δ(G) denote, respectively, its vertex set, edge set, number of vertices, maximum degree, and minimum degree. For x∈ V(G), let N_G(x) denote the set of neighbors of x in G and let d_G(x) denote the degree, i.e., the number of neighbors of x in G. A vertex of degree k is called a k—vertex.Let G be a graph, a k — vertex coloring f of G is an injection from V(G) to 1,2, …, k. If there is a k—vertex coloring of G, let V_i denote the vertices of G with color i(1≤ i≤ k), (V_i) denote the subgraph of G induced by V_i. We call f a k-tree coloring if (V_i) is a tree for every i(1≤ i ≤ k). The vertex arboricity of G, denoted by va(G), is the smallest number k for which there has a k—tree coloring of G. We call f a k—path coloring if every component of (V_i) is a path for every i(1 ≤i≤ k). The vertex linear arboricity of G, denoted by vla(G), is the smallest number k for which there has a k—path coloring of G. It is obvious that va(G) ≤ vla(G)≤x(G).Let u, v is two vertices of G, the distance between u and v, denoted by dist(u, v) is the length of the smallest path between u and v. The square graph G² of a graph G is the graph defined on the vertex set V(G) such that two vertices u and v are adjacent in G² if and only if 1≤ dist_G(u, v) ≤ 2.For planar graph, we haveTheorem 1 [32][33][34]If G is a planar graph, then x(G) ≤ 4.For the square graph of planar graph, Wegner [35] in 1977 conjectured the following. Conjucture 2 [35] Let G be a planar graph with maximum degree A, then[21] [22] [23] [24] have partially proved this conjecture.In this paper we mainly discuss the vertex arboricity and vertex linear arboricity of square graph. In the first section of this paper, we introduce some definitions about square graphs , vertex arboricity and vertex linear arboricity; in the second, the third, the fourth and the fifth sections, we discuss questions of the vertex arboricity and vertex linear arboricity of square graphs of tree, outerplanar graph, K₄ minor free graph and planar graph; in the last section of this paper we discuss the problem of the vertex arboricity and vertex linear arboricity of the Cartesian product of two complete graph. The main results of this paper is follows.1. If T is a tree with maximum degree Δ, then2. If G is an outerplanar graph with maximum degree Δ ≥ 6, then3. If G is a K₄ minor free graph with maximum degree Δ, then4. If G is a planar graph with maximum degree Δ, then5. If m = n = 2k(k ∈ Z⁺) , then va(k_m × k_n) = vla(k_m × k_n) = k + 1;...