d-退化图松弛均匀着色的一个注记(英文)

Note on Relaxed Equitable Coloring of d-Degenerate Graphs

松弛均匀着色是松弛着色的一类特殊情况,它要求任意两个色类的顶点数之差至多为1.d-退化图是指每个导出子图都存在度至多为d的顶点的图.证明了若顶点数位n的d-退化图G的最大度至多为△,且K≥18d,n≥17△.则G存在均匀(k-1,1)着色.

Relaxed equitable coloring of a graph is a special case of relaxed coloring which demands that the size of any two color classes differ by 1 at most. d-degenerate graph is a graph in which every induced sub-graph has a vertex with degree d at most. In this paper, we proved that every d-degenerate graph with maximum degree △ at most is equitably （k - 1,1 ） colorable for any k≥ 18d and n≥ 17△, so there is equitable coloring in G.