标题：Equitable vertex arboricity of graphs
作者：Wu, J.-L.;Zhang, X.;Li, H.
作者机构：[Wu, J.-L] School of Mathematics, Shandong University, Jinan 250100, China;[ Zhang, X] Department of Mathematics, Xidian University, Xi'an 710071, Chi 更多
通讯作者地址：[Wu, JL]Shandong Univ, Sch Math, Jinan 250100, Peoples R China.
关键词：Complete bipartite graph;Equitable coloring;k-tree-coloring;Planar graph;Vertex k-arboricity
摘要：An equitable (t,k)-tree-coloring of a graph G is a coloring of 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. The minimum t such that G has an equitable (~(t′),k)-tree-coloring for every ~(t′)≥t, denoted by vak≡(G), is the strong equitable vertex k-arboricity. In this paper, we give sharp upper bounds for va1≡(Kn,_n) and vak≡(Kn,_n), and prove 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.