关于欧拉公式在(3,1)*-列表着色中应用的一个注记

Note on the use of Euler's formula in(3,1)*-list coloring

如果对于图G的每个满足|L(v)|=k(其中v为G的任意顶点)的列表分配L,G都存在一个L-着色,使得G的每个顶点至多有d个邻居与其自己着有相同的颜色,则称图G是(k,d)*-可选的。在只用欧拉公式和图的结构性质研究2-连通平面图的(3,1)*-列表着色的基础上,研究欧拉公式在平面图的(3,1)*-列表着色中的应用,证明欧拉公式在研究有割点的平面图的(3,1)*-列表着色时也是有效的。

A graph G is called （k ,d）＊ -choosable if, for every list assignment L satisfying {L（v）}=k 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. Zhao and He first studied the （3,1） ＂ -list coloring of the 2-connected planar graphs just by using Euler＇s formula and the graph＇s structural proper- ties. The paper continues to investigate the use of Euler＇s formula in （3,1）＊ -list coloring the planar graphs, and shows that Euler＇s formula is also practicable in dealing with the planar graphs containing cut vertices.