最大度是6且不含有弦的小圈的可平面图的边染色

Edge Coloring of Planar Graphs With Δ=6 Without Short Cycles Contain Chords

对于最大度是Δ的可平面图G,如果χ'(G)=Δ,称G为第一类图;如果χ'(G)=Δ+1,称G为第二类图,χ'(G)表示G的边染色数.1965年,Vizing证明了任何一个Δ≥8的可平面图均是第一类图,并猜想Δ=6的可平面图也是第一类图.本文运用Discharge方法证明了最大度是6,且不含有弦的k-圈的可平面图是第一类图(4≤k≤7).

Let G be a planar graph of maximum degree △,G is said to be class 1 ifx＇（G） =△ and class 2 ifx＇（G） =△＋ 1, wherex＇（G） denotes the chromatic index of G. In 1965, Vizing proved that every planar graph of maximum degree at least eight is of class 1. By applying a Discharging method, we prove that every simple planar graph G with △ = 6 is of class 1, if G does not contain chordal-k-cycles （4≤k≤7）.