应用数学学报

作者：张巨峰, 陈敏, 王艺桥

单位：1 浙江师范大学数学科学学院, 金华 321004;<br>2 北京工业大学理学部, 北京 100124

关键词：平面图,非正常列表染色,$(k,d)^*$-可选,圈

令$G=(V,E)$是一个图.令$k$和$d$都是正整数.若能用$k$种颜色给图$G$的顶点染色使得每个顶点至多有$d$个邻点与其同色,则称$G$是$(k,d)^{*}$-可染的.给定图$G$的一个列表配置$L$,给每个$v\in V(G)$分配一个颜色列表$L(v)$.一个$(L,d)^{*}$-染色是指存在一个可给每个顶点$v\in V(G)$分配$\pi(v)\in L(v)$的映射$\pi$,使得$v$至多只有$d$个邻点与$v$染相同的颜色.如果每个$v\in V(G)$的颜色列表都满足$|L(v)|\ge k$时,图$G$有一个$(L,d)^{*}$-染色,那么称$G$是$(k,d)^{*}$-可选的.本文,我们证明了对所有的$i\in \{3,4\}$,每个不含相邻$i$-圈和$7$-圈的平面图是$(3,1)^{*}$-可选的.

来源：2026年第2期

《应用数学学报》期刊编辑部

查看应用数学学报杂志2026年第2期