mad■的图的均匀染色

摘要

图G的均匀k-染色是图G的一个正常k-点染色且满足任意2个色类的顶点数之差的绝对值至多为1。若G存在一个均匀k-染色，则称G是均匀k-可染的。图G的最大平均度是图G的所有非空子图的平均度的最大值，用mad(G)表示。本文运用权转移的方法证明mad■的图是均匀k-可染的，其中k≥max{Δ(G),6},且Δ(G)是图G的最大度。

关键词

均匀k-染色 / 最大平均度 / 权转移方法