# Minimum polychromatic number for plane graphs with fixed girth

For a plane graph $G$, let $g(G)$ denote the length of the shortest face in $G$. For a (not necessarily proper) $k$-coloring of $V(G)$ we say that a face is polychromatic if all $k$ colors appear on its vertices. A k-coloring of $V(G)$ is called polychromatic if every face of $G$ is polychromatic. The polychromatic number of $G$, denoted by $p(G)$, is the largest number $k$ such that there is a polychromatic $k$-coloring of $V(G)$. Define $p(g)=\min\{p(G)|g(G)=g\}$.

Determine $p(g)$ exactly for every positive integer $g$. The first open case is $g=5$ where we know that $2 \leq p(5) \leq 4$.

## Remarks

Alon et al. [1] showed that p(1)=p(2)=1, p(3)=p(4)=2 and for $g \geq 5,\ \lfloor \frac{3g-5}{4} \rfloor \leq p(g) \leq \lfloor \frac{3g+1}{4}\rfloor$. Recently, Markó Horváth gave an example that shows $p(5)\lt4$, hence only two possible values remain for p(5) (namely 2 or 3).

Horev et al. [2] proved that bipartite cubic plane graphs have a polychromatic 4-colouring.

## References

1. N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, Ph. Zumstein, Polychromatic Colorings of Plane Graphs, Discrete and Computational Geometry, 42(3):421-442, DOI link, author link
2. E. Horev, M.J. Katz, R. Krakovski, A. Nakamoto, Polychromatic 4-coloring of cubic bipartite plane graphs, Discrete Mathematics 312 (2012), 715–719, DOI link.