Polychromatic colorings of arbitrary rectangular partitions (Q1045138)

A \(k\)-colouring of the vertices of a plane graph is polychromatic if on every face all \(k\) colours appear at least once. The polychromatic number of a plane graph \(G\) is the maximum number \(k\) such that \(G\) admits a polychromatic \(k\)-colouring. A rectangular partition is a partition of an axis-parallel rectangle into an arbitrary number of non-overlapping axis-parallel rectangles such that no four rectangles meet at a common point. It is known that every rectangular partition admits a polychromatic 3-colouring. The present paper examines vertex-4-colurings of general partitions where every sub-rectangle is required to have all four colours appearing on its surfaces. It is shown that there are general partitions that do not admit such colourings. The problem to determine if a given general partition has such a 4-colouring is NP-complete.