Coloring of plane graphs with unique maximal colors on faces (Q2833253)

A capital vertex coloring of a plane graph \(G\) is a proper coloring using integers such that every face contains a unique vertex colored with the maximal color appearing on that face. The capital chromatic number \(\chi_C(G)\) of a plane graph \(G\) is the smallest \(k\) such that there exists a capital coloring using \(1\), \dots, \(k\). \textit{I. Fabrici} and \textit{F. Göring} [``Unique-maximum colouring of plane graphs'', Preprint (2013)] conjectured in 2013 that \(\chi_C(G) \leq 4\). This conjecture is stronger than the famous four color theorem. The authors of the paper proved that \(\chi_C(G) \leq 5\).NEWLINENEWLINEThe list version of capital coloring is also considered. A list assignment is a function \(L : V(G) \rightarrow \mathcal{P}(\mathbb{N})\). A graph \(G\) has a capital \(L\)-coloring if it has a capital coloring \(c : V(G) \rightarrow \mathbb{N}\) such that \(c(v) \in L(v)\) for every \(v \in V(G)\). We say that a graph \(G\) is capital \(k\) choosable if there is a capital \(L\)-coloring for all list assignments with \(|L(v)|\geq k\) for all \(v \in V(G)\). The minimum \(k\) such that \(G\) is capital \(k\)-choosable is denoted by \(\chi_C^l(G)\). The authors proved that \(\chi_C^l(G)\leq 7\) for every planar graph \(G\). They conjectured that their upper bound can be decreased to 5, this means \(\chi_C^l(G) \leq 5\).