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 is the largest number s.t. the nodes can be colored with 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 , we denote this value by . Define . An open problem is to determine for each . The first unknown case is when . However, there are only three candidates in this case: 2,3 or 4. It is worth mentioning that from the 4-color theorem would follow.
Recently, Markó Horváth gave an example that shows , hence only two possible values remain for p(5) (namely 2 or 3).