Problem of the month May 2011

In May, our open problem is related to the so-called polychromatic number of plane graphs. The polychromatic number of a plane graph [math]G[/math] is the largest number [math]k[/math] s.t. the nodes can be colored with [math]k[/math] different colors in such a way that each face becomes polychromatic, that is, each color appears on its vertices. For references, see our original open problem page on polychromatic number.

The length of the shortest face is clearly an upper bound for [math]k[/math], we denote this value by [math]g(G)[/math]. Define [math]p(g)=\min\{p(G)|g(G)=g\}[/math]. An open problem is to determine [math]p(g)[/math] for each [math]g\in\mathbb{Z}_+[/math]. The first unknown case is when [math]g=5[/math]. However, there are only three candidates in this case: 2,3 or 4. It is worth mentioning that from [math]p(5)=4[/math] the 4-color theorem would follow.

Update

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).