2-distance coloring of sparse planar graphs (Q2577174)

Let \(G = (V(G), E(G))\) be a graph without loops and multiple edges. Denote by \(d(u,v)\) the distance between vertices \(u\) and \(v\) of \(G\). A coloring \(f \: V(G) \to \{1, 2, \dots, k\}\) is said to be a 2-distance coloring if, for every two vertices \(u\) and \(v\) such that \(d(u,v)\leq 2\), the inequality \(f(u) \neq f(v)\) holds. The minimal number of colors among all 2-distance colorings of \(G\) is referred to as 2-distance chromatic number of \(G\) and denoted by \(\chi_2 (G)\). Obviously, if \(G\) is of maximal degree \(\Delta = \Delta (G)\) then \(\chi_2(G) \geq \Delta + 1\). The authors prove that if \(G\) is planar and its girth (the length of maximal cycle) is large enough (with respect to a fixed~\(\Delta\)) then \(\chi_2 (G) = \Delta +1\).