关于可平面图的3可选择性的一个注记

给图G=（V,E）的每个顶点v∈V分配一个可用色集L（v）,称L={L（v）｜v∈V}为G的一张色列表,若对每个顶点v∈V,都可以从L（v）中找到一种颜色φ（v）染给v,使得φ（x）≠φ（y）对任意边xy∈E成立,则称G是L可染的。若对G的任意一张满足｜L（v）｜≥k对所有v∈V成立的色列表L,G都是L可染的,则称G是k可选择的。本文运用Discharging方法证明了每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3可选择的。

A Note on 3-choosability of Planar Graphs

A list-assignment L of G=(V,E) is a collection of lists of available colors which assigns each vertex v of G a list of colors L(v).If we can choose a color φ(v) from L(v) for all vertex v∈V,such that φ(u)≠φv) whenever uv∈E,then we say that G is L-colorable.If G is L-colorable for every list-assignment L with |L(v)|≥k for each v∈V,then we say G is k-choosable.In this paper,we use the discharging method to prove that every planar graph with neither 4-,6-and 8-cycles nor triangles at distance less than 2 is 3-choosable.