标题: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
通讯作者地址:[Wu, JL]Shandong Univ, Sch Math, Jinan 250100, Peoples R China.
来源:Discrete mathematics
出版年:2013
卷:313
期:23
页码:2696-2701
DOI:10.1016/j.disc.2013.08.006
关键词: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.
收录类别:SCOPUS;SCIE
WOS核心被引频次:10
Scopus被引频次:8
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84883481913&doi=10.1016%2fj.disc.2013.08.006&partnerID=40&md5=4f8611d99b9b6c745fdf7496bbd33fbb
TOP