Equitable Vertex Arboricity Conjecture Holds for Graphs with Low Degeneracy

• 作者: Xin ZHANG Bei NIU Yan LI Bi LI
• 来源期刊: 数学学报（英文版）
• 年，卷（期）: 2021,（8）
• 页码范围: 1293-1302
• 页数: 10页
• 语种: 英文

摘要

The equitable tree-coloring can formulate a structure decomposition problem on the com-munication 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.