稀疏平面图的2-距离染色（英文）

2-distance Coloring of Sparse Planar Graphs

图G的k-2-距离染色是指一个映射φ:V(G)→{1,2,…,k},满足对任意距离小于等于2的顶点对u,v,有φ(u)≠φ(v).2-距离色数χ_2(G)是指使得图G是k-2-距离染色的最小的k.本文证明:对于g(G)≥5且△(G)≥44的平面图G,有χ_2(G)≤△(G)+4.

A k-2-distance coloring of a graph G is a mapping φ: V(G)→{1, 2,…,k},such that φ(u)≠φ(v) for every pair of vertices at distance at most two. The 2-distance chromatical of a graph G is the least integer k such that G has a k-2-distance coloring, denoted by X2(G). In this paper,we prove that X2(G)≤△(G)+ 4 for planar graphs with girth 5 and△(G)≥44.