摘要
给定图G的一个列表配置L,给每个v∈V(G)分配一个颜色列表L(v).一个(L,d)^(*)-染色是指存在一个可给每个顶点v∈V(G)分配π(v)∈L(v)的映射π,使得v至多只有d个邻点与v染相同的颜色.如果每个v∈V(G)的颜色列表都满足|L(v)|≥k时,图G有一个(L,d)^(*)-染色,那么称G是(k,d)^(*)-可选的.本文证明了每个不含相邻k-圈的平面图是(3,1)^(*)-可选的,其中k∈{3,4,5}.
Let G be a graph.A list assignment of G is a function L that assigns a list L(v)of colors to each vertex v∈V(G).An(L,d)^(*)-coloring of G is a mappingπthat assigns a colorπ(v)∈L(v)to each vertex v∈V(G)so that at most d neighbors of v receive the colorπ(v).If there exists an(L,d)^(*)-coloring for every list assignment L with|L(v)|≥k for all v∈V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k∈{3,4,5}.
作者
张巨峰
陈敏
王艺桥
ZHANG Jufeng;CHEN Min;WANG Yiqiao(College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua,Zhejiang,321004,P.R.China;School of Management,Beijing University of Chinese Medicine,Beijing,100029,P.R.Chin)
出处
《数学进展》
CSCD
北大核心
2023年第6期980-990,共11页
Advances in Mathematics（China）
基金
国家自然科学基金(Nos.11971437,12071048)
