最大度是5的可平面图的边染色

Edge colorings of planar graphs with maximum degree five

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.

Let G be a planar graph of maximum degree Δ,G was said to be class 1 if χ′（G）=Δ and class 2 if χ′（G）=Δ＋1,where χ′（G） denoted the chromatic index of G.In 1965,Vizing proved that planar graphs of class 1and class 2 were exist for Δ=5.By applying a discharging method,the author proved that every simple planar graph G with Δ=5 was of class 1,if G had no chordal-4-cycles and chordal-5-cycles,or no chordal-4-cycles and chordal-6-cycles.