子立方平面图的(1,0)-松弛强边列表染色

作者：张锦蓉; 陈敏^*; 王维凡

来源：数学进展, 2021, 50(05): 772-786.

• 子立方平面图
• 列表染色
• (1,0)-松弛强边染色
• (1,0)-松弛强边列表染色

令G=(V,E)是一个图.称图G是(1,0)-松驰强边k-可染的,是指存在映射π:E(G) → {1,2,…,k},使得E中的任意一条边e,满足颜色π(e)在e的1-邻域中至多出现1次,且在e的2-邻域中不出现.图G的(1,0)-松弛强边色数是使得G是(1,0)-松弛强边k-可染的最小正整数k的值.给图G中的每条边e配置一个颜色集合L(e),记L={L(e) | e ∈ E}.若存在一个(1,0)-松弛强边染色π,使得对每条边e都有π(e) ∈ L(e),则称G是(1,0)-松弛强边L-可染的.称染色π为G的一个(1,0)-松弛强边L-染色.当|L(e)| ≥ k且G是(1,0)-松弛强边L-可染的,称G是(1,0)-松弛强边k-可选的.本文证明了每个子立方平面图是(1,0)-松弛强边8-可选的.

• 单位
  浙江师范大学