On the weak 2-coloring number of planar graphs (Q2237215)

For a graph \(G = (V , E)\), a total ordering \(L\) on \(V\), and a vertex \(v \in V\) , let \(\mathrm{Wcol}_{2}[G, L, v]\) be the set of vertices \(w \in V\) for which there is a path from \(v\) to \(w\) whose length is 0, 1 or 2 and whose \(L\)-least vertex is \(w\). The weak 2-coloring number \(\operatorname{wcol}_{2}(G)\) of \(G\) is the least \(k\) such that there is a total ordering \(L\) on \(V\) with \(|\mathrm{Wcol}_{2}[G, L, v]| \leq k\) for all vertices \(v \in V\). \textit{J. van den Heuvel} et al. [Eur. J. Comb. 66, 129--144 (2017; Zbl 1369.05089)] proved that \(\operatorname{wcol}_{2}(G) \leq 30\), and this bound can be easily improved to 28. The authors of this paper improve this known upper bound on the weak 2-coloring number of planar graphs proving that every planar graph \(G\) satisfies \(\operatorname{wcol}_2(G) \leq 23\) and conjecture that this bound can be decreased to 18. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved. The conjecture, if true, would yield the best known upper bounds for both the star and star list chromatic number of planar graphs