TY - JOUR

T1 - Polychromatic colorings of arbitrary rectangular partitions

AU - Gerbner, Dániel

AU - Keszegh, Balázs

AU - Lemons, Nathan

AU - Palmer, Cory

AU - Pálvölgyi, Dömötör

AU - Patkós, Balázs

N1 - Funding Information:
The third author’s research was supported by the FIST (Finite Structures) project, in the framework of the European Community’s “Structuring the European Research Area” programme. The fifth and sixth author’s research was supported by OTKA NK 67867. The sixth author’s research was supported by National Science Foundation, Grant#: CCF-0728928.

PY - 2010/1/6

Y1 - 2010/1/6

N2 - 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.

AB - 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.

KW - Polychromatic colorings

KW - Rectangular partitions

UR - http://www.scopus.com/inward/record.url?scp=70350741365&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2009.07.019

DO - 10.1016/j.disc.2009.07.019

M3 - Article

AN - SCOPUS:70350741365

SN - 0012-365X

VL - 310

SP - 21

EP - 30

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -