摘要
图G称为 (k ,d) 可选的 ,如果对满足条件L(v) =k(v∈V(G) )的任意指派L ,存在G的一个L着色使得G的每一个顶点至多有d个邻点与之着同色 .本文证明了每个无 4 圈的平面图是 (4 ,1) 可选的 .
A graph G is called ( k,d ) choosable,if for every assignment L satisfying L(v) = k for all v∈V(G) ,there is an L coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself.In this paper we prove that every planar graph without 4 cycle is (4,1) choosable.
出处
《南京师大学报（自然科学版）》
CAS
CSCD
2000年第4期6-8,共3页
Journal of Nanjing Normal University(Natural Science Edition)
