Equitable Vertex Arboricity Conjecture Holds for Graphs with Low Degeneracy

被引：3

作者：

Zhang, Xin ^{[1
]}

Niu, Bei ^{[1
]}

Li, Yan ^{[1
]}

Li, Bi ^{[1
]}

机构：

[1] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2021年 / 37卷 / 08期

基金：

中国国家自然科学基金;

关键词：

Equitable coloring; tree-coloring; vertex arboricity; degeneracy; POINT-ARBORICITY; NETWORKS;

D O I：

10.1007/s10114-021-0663-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 Delta is equitably tree-k-colorable for every integer k >= (Delta + 1)/2 provided that Delta >= 9.818d, confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.

引用

页码：1293 / 1302

页数：10