2019/08/14 by Zhang, Xin, Niu, Bei, Li, Yan +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1908.05066
The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations. Namely, an equitable tree-k-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-k-colorable for every integer k≥ (Δ+1)/2 provided that Δ≥ 9.818d, confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.