无4-圈和5-圈的平面图的k-frugal列表染色

在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。

k-frugal list coloring of planar graphs without 4 and 5-cycles

For a graph G, c is a proper vertex coloring of G. If every color appears at most k-1 times in the neighbors of each vertex v, then c is called a k-frugal coloring of G. There are two conclusions on the k-frugal list coloring of planar graphs without 4 and 5-cycles:(1)For each planar graph without 4 and 5-cycles, if its maximum degree is Δ and Δ≥3k+8, then the k-frugal list chromatic number is less than or equal to 「(Δ)/(k-1)+2; (2)For each planar graph without 4 and 5-cycles, its k-frugal list chromatic number is no more than 「(Δ)/(k-1)+5.