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. A rectangular partition is a partition of a rectangle R into a set of non-overlapping
rectangles such that no four rectangles meet at a point. It was conjectured in [Y. Dinitz, MJ
Katz, R. Krakovski, Guarding rectangular partitions, in: 23rd European Workshop
Computational Geometry, 2007, pp. 30–33] that every rectangular partition admits a …