Minimum polychromatic number for plane graphs with fixed girth
For a plane graph [math]G[/math], let [math]g(G)[/math] denote the length of the shortest face in [math]G[/math]. For a (not necessarily proper) [math]k[/math]-coloring of [math]V(G)[/math] we say that a face is polychromatic if all [math]k[/math] colors appear on its vertices. A k-coloring of [math]V(G)[/math] is called polychromatic if every face of [math]G[/math] is polychromatic. The polychromatic number of [math]G[/math], denoted by [math]p(G)[/math], is the largest number [math]k[/math] such that there is a polychromatic [math]k[/math]-coloring of [math]V(G)[/math]. Define [math]p(g)=\min\{p(G)|g(G)=g\}[/math].
Determine [math]p(g)[/math] exactly for every positive integer [math]g[/math]. The first open case is [math]g=5[/math] where we know that [math]2 \leq p(5) \leq 4[/math].
Remarks
Alon et al. [1] showed that p(1)=p(2)=1, p(3)=p(4)=2 and for [math]g \geq 5,\ \lfloor \frac{3g-5}{4} \rfloor \leq p(g) \leq \lfloor \frac{3g+1}{4}\rfloor[/math]. Recently, Markó Horváth gave an example that shows [math]p(5)\lt4[/math], 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
- ↑ 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
- ↑ 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.
