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

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

设χ'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）=Δ.