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

摘要：

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

关键词：松弛均匀着色、d-退化图、d-退化顶点序列、贪心序列

所属期刊栏目：33

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目60903131

在线出版日期：2012-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：51-55