Colour Patterns for Polychromatic Four-colourings of Rectangular Subdivisions
Herman J. Haverkort, Maarten Löffler, Elena Mumford, Matthew J. O’Meara, Jack Scott Snoeyink, Bettina Speckmann · Deep Blue (University of Michigan) · 2022
A non-degenerate rectangular subdivision is a subdivision of a rectangle into a set of non-overlapping rectangles S, such that no four rectangles meet in a point. We consider a problem that Katz and colleagues call strong polychromatic four-colouring: Colouring the vertices of the subdivision with four colours, such that each rectangle of S has all colours among its four corners. By considering the possible colouring patterns, we can give short constructive proofs of colourability for subdivisions that are sliceable or one-sided. We also present techniques and observations for nonsliceable, two-sided subdivisions.