On list \(r\)-hued coloring of planar graphs
type: Item
instance of: scholarly article
title: On list \(r\)-hued coloring of planar graphs
zbMATH Open document ID: 1385.05035
author: Peng Zhang
published in: Journal of Combinatorial Optimization
publication date: 2017-11-16T00:00:00Z
review text: 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 …
reviewed by: Colton Magnant
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 6807518
zbMATH Keywords: \(r\)-hued coloring
zbMATH Keywords: list \(r\)-hued coloring
zbMATH Keywords: planar graphs
zbMATH Keywords: Wagner's conjecture
MaRDI profile type: Publication
full work available at URL: s10878-017-0118-0
OpenAlex ID: W2591492772
cites work: On the list dynamic coloring of graphs
cites work: Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable
cites work: Q5422499
cites work: Choosability of the square of planar subcubic graphs with large girth
cites work: On dynamic coloring for planar graphs and graphs of higher genus
cites work: List Colouring Squares of Planar Graphs
cites work: Q3115232
cites work: Q5466088
cites work: Conditional colorings of graphs
cites work: A bound on the chromatic number of the square of a planar graph
cites work: On \(r\)-hued coloring of \(K_4\)-minor free graphs
DOI: 10.1007/S10878-017-0118-0
Recommended article: On list \(r\)-hued coloring of outer-1-planar graphs
Recommended article: On \(r\)-hued coloring of planar graphs
Recommended article: List colourings of planar graphs
Recommended article: List colourings of planar graphs. (Reprint)
Recommended article: Multiple list colouring of planar graphs
Recommended article: On list-coloring outerplanar graphs
Recommended article: List injective coloring of planar graphs
Recommended article: Upper bounds of \(r\)-hued colorings of planar graphs
description: scientific article; zbMATH DE number 6807518