Equitable Vertex Arboricity Conjecture Holds for Graphs with Low Degeneracy  

作　　者：Xin ZHANG Bei NIU Yan LI Bi LI 

机构地区：[1]School of Mathematics and Statistics,Xidian University,Xi’an 710071,P.R.China

出　　处：《Acta Mathematica Sinica,English Series》2021年第8期1293-1302,共10页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11871055,11701440)。

摘　　要：The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one.In this paper,we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-fc-colorable for every integer k≥(Δ+1)/2 provided that Δ≥9.818d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.

关 键 词：Equitable coloring tree-coloring vertex arboricity DEGENERACY 

分 类 号：O157.5[理学—数学]