Polychromatic colorings of rectangular partitions

Darko Dimitrov, Elad Horev, Roi Krakovski

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

7 ציטוטים ‏(Scopus)

תקציר

A rectangular partition is a partition of a plane rectangle into an arbitrary number of non-overlapping rectangles such that no four rectangles share a corner. In this note, it is proven that every rectangular partition admits a vertex coloring with four colors such that every rectangle, except possibly the outer rectangle, has all four colors on its boundary. This settles a conjecture of Dinitz et al. [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: Abstracts 23rd Euro. Workshop Comput. Geom., 2007, pp. 30-33]. The proof is short, simple and based on 4-edge-colorability of a specific class of planar graphs.

שפה מקוריתאנגלית
עמודים (מ-עד)2957-2960
מספר עמודים4
כתב עתDiscrete Mathematics
כרך309
מספר גיליון9
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 6 מאי 2009
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Polychromatic colorings of rectangular partitions'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי