Polychromatic 4-coloring of guillotine subdivisions

Elad Horev, Matthew J. Katz, Roi Krakovski, Maarten Löffler

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

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

תקציר

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.

שפה מקוריתאנגלית
עמודים (מ-עד)690-694
מספר עמודים5
כתב עתInformation Processing Letters
כרך109
מספר גיליון13
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 יוני 2009
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Polychromatic 4-coloring of guillotine subdivisions'. יחד הם יוצרים טביעת אצבע ייחודית.

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