Minimum 2-distance coloring of planar graphs and channel assignment (Q724734)

A 2-distance \(k\)-coloring of a graph \(G\) is a \(k\)-coloring such that any two distinct vertices at distance at most two get different colors. This coloring naturally arises from a problem known as the channel assignment problem. The minimum number of colors needed for such a coloring is called the 2-distance chromatic number and denoted as \(\chi_2(G)\). For planar graphs this number was firstly investigated in [\textit{G. Wegner}, Graphs with given diameter and a coloring problem. Techn. Rep., Univ. Dortmund (1977)]. Later, many other results and conjectures were presented. As the main results of this paper, the authors prove the following two theorems. Theorem 1. If \(G\) is a planar graph with maximum degree \(\Delta \leq 5\), then \(\chi_2(G) \leq 20\). Theorem 2. If \(G\) is a planar graph with maximum degree \(\Delta \geq 6\), then \(\chi_2(G) \leq 5 \Delta -7\). Both theorems are proved by induction on the number of vertices and edges. In particular, some properties of a counterexample with the smallest number of vertices and edges are first investigated in both proofs. Then, a weight function \(w\) is defined on the vertices and faces of the graph. Finally, some discharging rules are defined to redistribute these weights. When the discharging is finished, a new weight is obtained and an obvious contradiction occurs.