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

doi:10.1016/j.disc.2009.07.019

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

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 language	English
Pages (from-to)	21-30
Number of pages	10
Journal	Discrete Mathematics
Volume	310
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2009.07.019
State	Published - Jan 6 2010

Keywords

Polychromatic colorings
Rectangular partitions

Access to Document

10.1016/j.disc.2009.07.019

Cite this

@article{ff07152f661542a8a54aa6ba5181b3d9,

title = "Polychromatic colorings of arbitrary rectangular partitions",

abstract = "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.",

keywords = "Polychromatic colorings, Rectangular partitions",

author = "D{\'a}niel Gerbner and Bal{\'a}zs Keszegh and Nathan Lemons and Cory Palmer and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi and Bal{\'a}zs Patk{\'o}s",

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

year = "2010",

month = jan,

day = "6",

doi = "10.1016/j.disc.2009.07.019",

language = "English",

volume = "310",

pages = "21--30",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

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 -

Polychromatic colorings of arbitrary rectangular partitions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this