Wegner's conjecture on 2-distance coloring for planar graphs (Q2152439)

This 4-page article is an attempt to solve Wegner's conjecture, which can be traced back to 1977, to a certain extent. More precisely, the authors investigate the upper bound on Wegner's conjecture for a planar graph \(G\) with maximum degrees \(7\) and \(8\), where the conjecture is stated as ``Let \(G\) be a planar graph with maximum degree \(\Delta \). If \(4 \le \Delta \le 7\), then \(\chi_2(G) \le \Delta +5\). If \(\Delta \ge 8\), then \(\chi_2(G) \le \lfloor \frac{3\Delta }{2} \rfloor +1 \)''. Let \(d(u, v)\) be the distance between the two vertices \(u\) and \(v\) of a graph \(G\). A \(2\)-distance \(k\)-coloring of \(G\) is a function \(f: V (G) \to \{1, 2,\dots,k\}\) such that \(| f (u) - f (v)| \ge 1\) if \(1 \le d(u, v) \le 2\). The \(2\)-distance chromatic number of \(G\), denoted as \(\chi_2(G)\), is the minimum \(k\) such that \(G\) has such a coloring. The main theorem of this paper is stated as ``If G is a planar graph with \(7 \le \Delta(G) \le 8\), then \(\chi_2(G) \le 5 \Delta(G)-9\)''. It partially improves the results proven earlier, namely the results, i) \(\chi_2(G) \le 28 \), if \( \Delta(G) = 7\) and ii) \(\chi_2(G) \le 32\), if \(\Delta(G)= 8\). Checking degrees of the vertices, \(d(v)\)s, and of faces, \(d(f)\)s, for various values with the help of discharging rules they proved the theorem. There are \(7\) lemmas and a proposition to support the main theorem. The Lemmas are: \begin{itemize} \item[(1)] \(G\) is \(2\)-connected. \item[(2)] \(\delta(G) \ge 3\), where \(\delta\) denotes the minimum degree of a vertex. \item[(3)] Every \(3\)-vertex is adjacent to three \(\Delta\)-vertices. \item[(4)] Every \(3\)-face is either a \((4,\Delta, \Delta)\)-face or a \((5^+, 5^+, 5^+)\)-face. \item[(5)] Every \(3\)-vertex is incident with at least two \(5^+\)-faces \item[(6)] Every \(4\)-vertex is incident to at most one \(3\)-face. \item[(7)] Every \(5\)-vertex is incident to at most four \(3\)-face. If \(5\)-vertex \(v \) is incident to four \(3\)-faces, then \(v\) is adjacent to at least four \(\Delta\)-vertices. \end{itemize} and the Proposition is: For an edge \(uv\), let \(H = G/uv\) be the graph obtained from \(G\) by contracting the edge \(uv\) and \(v^\prime\) be the new vertex in \(H\) obtained by contracting the edge \(uv\). After the operation \(G/uv\), the following properties of the vertex degree are formulated: \par 1) \(d_H (w) \le d_G(w)\) for each vertex \(w \in V (H) \setminus \{v^\prime\}\) and \( d_H (v^\prime) = d_G(u) + d_G(v) - 2 - t_G(uv)\), where \(t_G(uv)\) is the number of \(3\)-faces incident with the edge \(uv\). \par 2) For any vertices \( w, w^\prime \in V (H) \setminus \{v^\prime\}, d_H(w, w^\prime) \le d_G(w, w^\prime)\) and \(d_H (w, v^\prime) \le d_G(w, u)\). The authors use the techniques of contracting edges and discharging methods to get the desired solution. That is, they design appropriate discharging rules and redistribute weights accordingly to reduce the limit of the upper bound of Wegner's conjecture. Though several upper bounds in terms of maximum degree are proved and some results are improved, the conjecture still remains an open problem. So there is wide scope for interested researchers to work on it. This paper stands as a guiding step for them.