欧拉公式的一个应用

A use of Euler's formula

对于图G的所有顶点v∈V(G)的每个满足|L(v)|=m的列表分配L,如果G总存在一个L-染色,使得G的每个顶点至多有d个邻点与它自己染相同的颜色,则称图G是d-缺陷m-可选的。Ko-wei Lih等结合欧拉公式用放电的方法证明了每个不含4-圈和i-圈的平面图是1-缺陷3-可选的,其中i∈|5,6,7|。对于2-连通图,只用欧拉公式就能证明他们的结果。

A graph G is called m-choosable with impropriety d if, for every list assignment L satisfying ｜L（v）｜= m for all v∈V（G）, there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. Ko-Wei Lih and others used Euler＇s formula and the way of discharging to prove that every planar graph without 4-cycles and i-cycles for some i∈ {5,6,7} is （3,1） - choosable. For any 2-connected G, these results can be proved just by using Euler＇s formula.