ملخص
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 |
| المعرِّفات الرقمية للأشياء | |
| حالة النشر | نُشِر - 15 يونيو 2009 |
| منشور خارجيًا | نعم |
بصمة
أدرس بدقة موضوعات البحث “Polychromatic 4-coloring of guillotine subdivisions'. فهما يشكلان معًا بصمة فريدة.قم بذكر هذا
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver