图的无圈染色

我们证明最大度Δ≥5的图的无圈色数至多是a(G)≤L(Δ-1)2/2」,这个结果比目前公认的最小上界a(G)=Δ(0-1)/2要小。同时得出两个新的结论:对任意Δ=5的图G,有a(G)≤8;对任意Δ=6的图G,有a(G)≤12。     

没有K_5-子式的图是无圈5-可染的

2006年,Borodin证明了所有平面图都可以无圈5-可染。本文推广Borodin的结果到没有K5-子式的图。