Equitable vertex arboricity of graphs

Original · EN

An equitable (t,k,d)-tree-coloring of a graph G is a coloring to vertices of G such that the sizes of any two color classes differ by at most one and the subgraph induced by each color class is a forest of maximum degree at most k and diameter at most d. The minimum t such that G has an equitable (t',k,d)-tree-coloring for every t'≥ t is called the strong equitable (k,d)-vertex-arboricity and denoted by va≡ₖ,d(G). In this paper, we give sharp upper bounds for va≡₁,₁(Kₙ,ₙ) and va≡ₖ,∞(Kₙ,ₙ) by showing that va≡₁,₁(Kₙ,ₙ)=O(n) and va≡ₖ,∞(Kₙ,ₙ)=O(n/²) for every k≥ 2. It is also proved that va≡∞,∞(G)≤ 3 for every planar graph G with girth at least 5 and va≡∞,∞(G)≤ 2 for every planar graph G with girth at least 6 and for every outerplanar graph. We conjecture that va≡∞,∞(G)=O(1) for every planar graph and va≡∞,∞(G)≤ Δ(G)+1/2 for every graph G.