齐林明, 李金波, 李卫奇
QI Lin-ming[1], LI Jin-bo[2], LI Wei-qi[2]
摘要:
对于整数 k,r>0 , 图 G 的 (k,r) 染色是一个正常 k 染色, 使得对于每一个度数为 d(v) 的点 v , v 的邻点至少表现 min{d(v),r}种颜色, 这样的染色, 称之为 r-hued 染色, 图 G 的 r-hued 染色数, 记作 χr(G), 是使图 G 存在 (k,r) 染色的最小的 k 值. 在这篇文章中, 证明了, 对于一般平面图 G, χ3(G)≤12.