TY - JOUR
T1 - Polychromatic 4-coloring of guillotine subdivisions
AU - Horev, Elad
AU - Katz, Matthew J.
AU - Krakovski, Roi
AU - Löffler, Maarten
PY - 2009/6/15
Y1 - 2009/6/15
N2 - A polychromatic k-coloring of a plane graph G is an assignment of k colors to the vertices of G such that each face of G, except possibly for the outer face, has all k colors on its boundary. A rectangular partition is a partition of a rectangle R into a set of non-overlapping rectangles such that no four rectangles meet at a point. It was conjectured in [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: 23rd European Workshop Computational Geometry, 2007, pp. 30-33] that every rectangular partition admits a polychromatic 4-coloring. In this note we prove the conjecture for guillotine subdivisions - a well-studied subfamily of rectangular partitions.
AB - A polychromatic k-coloring of a plane graph G is an assignment of k colors to the vertices of G such that each face of G, except possibly for the outer face, has all k colors on its boundary. A rectangular partition is a partition of a rectangle R into a set of non-overlapping rectangles such that no four rectangles meet at a point. It was conjectured in [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: 23rd European Workshop Computational Geometry, 2007, pp. 30-33] that every rectangular partition admits a polychromatic 4-coloring. In this note we prove the conjecture for guillotine subdivisions - a well-studied subfamily of rectangular partitions.
KW - Algorithms
KW - Combinatorial and computational geometry
KW - Guillotine subdivisions
KW - Polychromatic coloring
UR - http://www.scopus.com/inward/record.url?scp=67349114200&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2009.03.006
DO - 10.1016/j.ipl.2009.03.006
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:67349114200
SN - 0020-0190
VL - 109
SP - 690
EP - 694
JO - Information Processing Letters
JF - Information Processing Letters
IS - 13
ER -