Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. $$\chi _{2}(G)$$ χ 2 ( G ) =min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree $$\Delta $$ Δ , $$\chi _2(G) \le 7$$ χ 2 ( G ) ≤ 7 if $$\Delta \le 3$$ Δ ≤ 3 , $$\chi _2(G) \le \Delta +5$$ χ 2 ( G ) ≤ Δ + 5 if $$4\le \Delta \le 7$$ 4 ≤ Δ ≤ 7 and $$\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1$$ χ 2 ( G ) ≤ ⌊ 3 Δ 2 ⌋ + 1 if $$\Delta \ge 8$$ Δ ≥ 8 . In this paper, we prove that: (1) If G is a planar graph with maximum degree $$\Delta \le 5$$ Δ ≤ 5 , then $$\chi _{2}(G)\le 20$$ χ 2 ( G ) ≤ 20 ; (2) If G is a planar graph with maximum degree $$\Delta \ge 6$$ Δ ≥ 6 , then $$\chi _{2}(G)\le 5\Delta -7$$ χ 2 ( G ) ≤ 5 Δ - 7 .