摘要
对于一个给定的平面图G,确定G是否为3-列表可染的是NP-困难的.运用D ischarging方法,证明了一个平面图是3-列表可染的充分条件,即不含相交i-圈与j-圈(4≤i≤j≤6),且三角形与5--圈的距离至少为3的平面图是3-列表可染的.所证结果改进了现有文献的相关结果.
For any given planar graph G,it was NP-hard to determine whether it could be 3-list-colorable.Using the Discharging method,it was given a sufficient condition for planar graphs to be 3-list-colorable.It was showed that every planar graph would be 3-list-colorable if it contained neither triangles and 5--cycles at distance less than 3 nor intersecting i-cycles and j-cycles where 4≤i≤j≤6.This improved the known results.
出处
《浙江师范大学学报（自然科学版）》
CAS
2009年第4期416-420,共5页
Journal of Zhejiang Normal University:Natural Sciences
基金
浙江省教育厅科研项目(20070441)
关键词
列表染色
可平面图
圈
距离
list-coloring planar graph cycles distance
