On list \(r\)-hued coloring of planar graphs (Q1680495)

Let \(k\) and \(r\) be positive integers and let \(G\) be a graph. Given a vertex \(v \in V(G)\), let \(N_{G}(v)\) denote the neighborhood in \(G\) of \(v\), let \(d(v) = |N_{G}(v)|\) be the degree of \(v\), and let \(\chi(G)\) and \(\chi_{\ell}(G)\) denote the chromatic number and list chromatic number of \(G\) respectively. For a map \(\phi : V(G) \rightarrow [k]\) and a set \(V^\prime \subseteq V(G)\), define \(\phi(V^\prime) = \{\phi(v) : v \in V^\prime\}\). Then an \(r\)-hued coloring of the graph \(G\) is such a mapping \(\phi\) such that \(\phi(x) \neq \phi(y)\) for every edge \(xy \in E(G)\) and \(|\phi(N_{G}(v))| \geq \min \{ d(v), r\}\) for every vertex \(v \in V(G)\). In other words, this is a proper coloring in which each vertex with degree at least \(r\) has \(r\) different colored neighbors, or otherwise the vertex has all different colored neighbors. Given a fixed positive integer \(r\), the \(r\)-hued chromatic number of \(G\), denoted by \(\chi_{r}(G)\), is the smallest integer \(k\) for which \(G\) has an \(r\)-hued coloring using \(k\) colors. Given a mapping \(L\) that assigns a list of available colors for each vertex \(v\), the list \(r\)-hued chromatic number of \(G\), denoted by \(\chi_{L, r}(G)\) is the minimum integer \(k\) such that whenever \(|L(v)| = k\) for all \(v\), there exists an \(r\)-hued coloring of \(G\) using only colors chosen from the list assigned to each vertex. The authors provide the following upper bounds on \(\chi_{L, r}(G)\), \(\chi_{\ell}(G^{2})\), \(\chi(G^{2})\), and \(\chi_{r}(G)\) for planar graphs without \(4\)-cycles. Theorem 1. If \(G\) is a planar graph without \(4\)-cycles, then \[ \chi_{L, r}(G) \leq \max\{40, r + 8\}. \] Theorem 2. If \(G\) is a planar graph without \(4\)-cycles, then \[ \chi_{\ell}(G^{2}) \leq \max\{40, \Delta(G) + 8\}. \] Theorem 3. If \(G\) is a planar graph with \(\Delta(G) \geq 26\) and without \(4\)-cycles, then \[ \chi(G^{2}) \leq \lfloor 3\Delta(G) / 2 \rfloor + 1. \] Theorem 4. If \(G\) is a planar graph without \(4\)-cycles and \(r \geq 26\), then \[ \chi_{r}(G) \leq \lfloor 3r / 2 \rfloor + 1. \] The proofs use the structure of planar graphs and the lack of \(4\)-cycles to form the basis of a discharging argument.