Minimum polychromatic number for plane graphs with fixed girth

Definitions and mathematical statement

Let $G$ be a finite plane graph with its embedding fixed, and let $V(F)$ be the set of vertices incident with a face $F$, including the outer face. A map $c:V(G)\to\{1,\ldots,k\}$ is polychromatic if \[ \{c(v):v\in V(F)\}=\{1,\ldots,k\}\quad\text{for every face }F. \] Adjacent vertices may have the same color. Define $p(G)$ as the largest positive integer $k$ for which such a coloring exists. Let $g(G)$ be the length of a shortest face, in the source's terminology, and set \[ p(g)=\min\{p(G):g(G)=g\}. \] This parameter concerns face length, not necessarily the length of the shortest graph cycle. The graph class and the treatment of repeated vertices or edges in face boundaries must be fixed: boundary-walk length with multiplicity and the cardinality $|V(F)|$ differ when a face boundary repeats vertices.

Problem. Determine $p(g)$ exactly for every positive integer $g$. The source's original first-open-case bound is $2\leq p(5)\leq4$. The supplied research summary reports the later refinement \[ 2\leq p(5)\leq3, \] so it leaves $p(5)\in\{2,3\}$ unresolved. It also reports \[ p(1)=p(2)=1,\qquad p(3)=p(4)=2, \] and, for $g\geq5$, \[ \left\lfloor\frac{3g-5}{4}\right\rfloor \leq p(g)\leq \left\lfloor\frac{3g+1}{4}\right\rfloor. \] The quantifier $g(G)=g$ is exact, not $g(G)\geq g$. The small cases and stated results must be interpreted in the source's graph and face-length conventions rather than silently imposed on a different restricted class.

Short English statement

Find the minimum possible number of colors that can appear on every face of a plane graph with prescribed shortest-face length. The supplied updated first case is $p(5)=2$ or $3$, and face length must be distinguished from graph girth.

Sources

• Egres Open, Minimum polychromatic number for plane graphs with fixed girth, listed at https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems; HTML extraction, accessed 2026-07-29. The archived index is not a current resolution authority according to the record.
• Alon and collaborators, the small values, general bounds, and NP-completeness of deciding $p(G)\geq3$; Markó Horváth, the reported example giving $p(5)<4$; Horev and collaborators, a polychromatic four-coloring result for bipartite cubic plane graphs. These are the supplied attributions, without publication titles, years, or theorem identifiers.
• Local registry data/unsolvedmath/problems.json, permanent ID $3000057$, source code catalogue entry, Minimum polychromatic number for plane graphs with fixed girth. The record labels this partially solved and PARTIAL-PROGRESS, with NEEDS_REVIEW source-status and rights qualifications; no redistribution license was displayed in the archived footer according to the record.