松弛均匀着色是松弛着色的一类特殊情况，它要求任意两个色类的顶点数之差至多为1．d-退化图是指每个导出子图都存在度至多为d的顶点的图．证明了若顶点数位rt的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.
展开▼
