笛卡儿积图的2-hued列表染色

摘要

给定图G的一个列表分配L,图G的一个(L,r)-染色,是一个正常染色c满足:每个顶点v都至少和min{d(v),r}种不同颜色的顶点相邻,并且c(v)属于L(v).图G的r-hued列表染色数,记为χL,r(G),是最小正整数k满足对于任意一个|L(v)|=k的列表分配L,图G有一个(L,r)-染色.最后证明了χL,2(Pm□Pn)=4,并且确定了χL,2(Pm□Cn)的范围．

关键词

路 / 圈 / 笛卡儿积图 / 2-hued列表染色