On the equitable vertex arboricity of graphs
Fangyun Tao, Wensong Lin · International Journal of Computer Mathematics · 2015
An equitable (t,k)-tree-colouring of a graph G is a t-colouring of vertices of G such that the sizes of any two colour classes differ by at most one and the subgraph induced by each colour class is a forest of maximum degree at most k. The strong equitable vertex k-arboricity, denoted by vak≡(G), is the smallest t such that G has an equitable (t′,k)-tree-colouring for every t′≥t. In this paper, we give upper bounds for va1≡(G) when G is a balanced complete bipartite graph Kn,n and n≡0,1(mod3). For some special cases, we determine the exact values. We also prove that: (1) va∞≡(G)≤12 for every planar graph without 4-cycles, 5-cycles and 6-cycles; (2) va∞≡(G)≤6 for every planar graph with neither 3-cycles nor adjacent 4-cycles.