Cyclic colorings of 3-polytopes with large maximum face size (Q2784508)

The cyclic chromatic number \(\chi_c\) of a plane graph \(G\) is the chromatic number of the dual graph of \(G\). That is, the minimum number of colours that allow a vertex colouring of \(G\) so that no face of \(G\) has two vertices of the same colour. The maximum face size \(\Delta^*\) of \(G\) is a natural lower bound on the cyclic chromatic number. It is conjectured that \(\chi_c\leq 3/2\cdot\Delta^*\), and it is known that \(2\Delta^*\) is an upper bound on \(\chi_c\). For \(3\)-connected plane graphs (or for \(1\)-skeletons of \(3\)-polytopes), it is known that \(\chi_c\leq \Delta^*+\)constant. The authors prove that \(\chi_c\leq\Delta^*+1\) if \(\Delta^*\geq 122\) and \(\chi_c\leq\Delta^*+2\) if \(\Delta^*\geq 61\). The proof is based on a charge-redistribution argument.