• Calendar

January 23, Wednesday
12:00 – 13:00

A polychromatic $k$ - coloring of a plane graph $G$ is an assignment of k colors to the vertices of $G$, such that each face of $G$, except possibly for the outer face, has all $k$ colors on its boundary. Polychromatic colorings of plane graphs are an essential tool for guarding and covering problems. In a polychromatic coloring of a plane graph $G$ every color class is present on every face of $G$. Therefore, any color class forms a set of vertex guards for the faces of $G$.

We survey recent results concerning polychromatic colorings, and prove that every 2-connected plane bipartite cubic graph admits a polychromatic $4$-coloring.