Polychromatic colorings of arbitrary rectangular partitions

Dániel Gerbner, Balázs Keszegh, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, Balázs Patkós

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. This paper examines vertex 4-colorings of general partitions where every subrectangle is required to have all four colors appear on its boundary. It is shown that there exist general partitions that do not admit such a coloring. This answers a question of Dimitrov et al. [D. Dimitrov, E. Horev, R. Krakovski, Polychromatic colorings of rectangular partitions, Discrete Mathematics 309 (2009) 2957-2960]. It is also shown that the problem to determine if a given general partition has such a 4-coloring is NP-Complete. Some generalizations and related questions are also treated.

Original languageEnglish
Pages (from-to)21-30
Number of pages10
JournalDiscrete Mathematics
Issue number1
StatePublished - Jan 6 2010


  • Polychromatic colorings
  • Rectangular partitions


Dive into the research topics of 'Polychromatic colorings of arbitrary rectangular partitions'. Together they form a unique fingerprint.

Cite this