Δ≥9且不含相邻4-圈的平面图是(Δ+1)-全可选和Δ-边可选的  

Planar Graph with Δ≥9 and without Adjacent 4-cycles is List Edge Δ-colorable and List Totally(Δ+1)-colorable

作　　者：卢秋丽[1] 王应前[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《安庆师范学院学报（自然科学版）》2012年第3期21-27,共7页Journal of Anqing Teachers College(Natural Science Edition)

基　　金：浙江省自然科学基金项目(Y6090699)资助

摘　　要：设χ'l(G),χ″l(G)和Δ(G)分别表示平面图G的列表色数,列表全色数和最大度,目前已经证明:若G是Δ≥12的平面图,则χ'l(G)=Δ,χ″l(G)=Δ+1。本文将证明:若G是Δ≥9且不含相邻4-圈的平面图,则χ″l(G)=Δ+1,χ'l(G)=Δ。Let χ′l（G）,χ″l（G） and Δ（G） denote the list chromatic index,the list total chromatic nomber and the maximum degree of a graph G,respectively.It is known that if G is a planar graph with Δ≥12 then χ′l（G）=Δ,χ″l（G）=Δ＋1.In this paper,we show that if G is a planar graph with Δ≥9 and without adjacent 4-cycles then χ″l（G）=Δ＋1 and χ′l（G）=Δ.

关 键 词：平面图 相邻4-圈 边列表染色 全列表染色 最大度 

分 类 号：O157.5[理学—数学]