关于可平面图的3-列表染色的一个注记

• 来源期刊: 浙江师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 列表染色 可平面图 圈 距离
• 年，卷（期）: 2009,（4）
• 所属期刊栏目: 数学
• 页码范围: 416-420
• 页数: 5页
• 分类号: O157.5
• 字数: 3633字
• 语种: 中文

摘要

对于一个给定的平面图G,确定G是否为3-列表可染的是NP-困难的.运用Discharging方法,证明了一个平面图是3-列表可染的充分条件,即不含相交i-圈与j-圈(4≤i≤j≤6),且三角形与5--圈的距离至少为3的平面图是3-列表可染的.所证结果改进了现有文献的相关结果.