基本信息

---

下载

文档摘要

---

平面图的2-距离染色问题

摘要

2-距离染色是图论中的一种染色问题,由Wegner首次提出并研究.图G的一

个k-2-距离染色是指映射φ:V(G)→{1,2,···,k}满足对任意距离小于等于2的点

对u,v,有φ(u)=?φ(v).图G的2-距离色数是使得图G有一个k-2-距离染色的最小

的正整数k,表示为χ2(G).

1977年,Wegner提出猜想：对于平面图G,若?(G)