不含4-圈平面图的2-距离染色

摘要

图G的2-距离染色是指映射φ:V(G)→{1,2,...,k},使得距离不超过2的顶点染不同的颜色,即若0＜ dG(u,v)≤2,则φ(u)≠φ(v).图G的2-距离色数是使G有一个k-2-距离染色的最小正整数k,记为x2(G).本文证明了不合4-圈且△(G)≥10的平面图G是(△(G)+ 10)-2-距离可染的.%A 2-distance coloring of a graph G is a function φ:V(G)-→ {1,2,…,k},such that φ(u) ≠ φ(v) if 0 ≤ dG(u,v) ≤ 2.The 2-distance chromatic number of G is the minimum integer k which satisfies that G has a k-2-distance coloring,denoted by x2(G).In this paper,we prove that planar graphs with △(G) ≥ 10 and without 4-cycles is (△(G) + 10)-2-distance colorable.