摘要
图G的k-2-距离染色是指映射c:V(G)→{1,2,…,k},使得对G中满足0<d_G(u,v)≤2的点对u,v,有c(u)≠c(v).称χ_2(G)=min{k|G有一个k-2-距离染色}为G的2-距离色数.本文证明了不含3,4,8-圈,且△≥14的平面图是(△+5)-2-距离可染的.
The k-2-distance coloring of a graph G is a mapping c:V(G)→ {1,2,…,k}such that for every pair of u,v satisfying 0 < d_G(u,v) ≤ 2,c(u) ≠ c(v).The minimum number of colors in 2-distance coloring of G is its 2-distance chromatic number,denoted by χ_2(G).In this paper,we prove that every planar graph without 3,4,8-cycles and △ ≥ 14 is(△ + 5)-2-distance colorable.
出处
《数学进展》
CSCD
北大核心
2015年第2期208-218,共11页
Advances in Mathematics（China）
基金
Supported partially by NSFC(No.11271334)
ZJNSF(No.Z6110786)
关键词
平面图
最大度
2-距离染色
planar graph
maximum degree
2-distance coloring
