-
题名最大度为4的图的无圈列表边染色
- 1
-
-
作者
王娟
苗连英
蔡建生
-
机构
曲阜师范大学管理学院
中国矿业大学数学学院
潍坊学院数学与信息科学学院
-
出处
《数学学报（中文版）》
CSCD
北大核心
2022年第1期153-160,共8页
-
基金
国家自然科学基金资助项目(11771443,12071351)。
-
文摘
对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e_(1),e_(2)满足φ(e_(1))≠φ(e_(2)),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a'_(l)(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a'_(l)(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.
-
关键词
边染色
无圈染色
列表染色
最大度
-
Keywords
edge coloring
acyclic coloring
list coloring
maximum degree
-
分类号
O157.5
[理学—数学]
-
