Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ipl.2009.03.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
polychromatic 4-coloring,k color,outer face,guillotine subdivision,plane graph g,polychromatic k-coloring,y. dinitz,european workshop computational geometry,m.j. katz,rectangular partition,computational geometry,algorithms,plane graph | Discrete geometry,Discrete mathematics,Combinatorics,Vertex (geometry),Rectangle,Computational geometry,Subdivision,Partition (number theory),Conjecture,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
109 | 13 | 0020-0190 |
Citations | PageRank | References |
3 | 0.43 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elad Horev | 1 | 22 | 3.75 |
| Matthew J. Katz | 2 | 225 | 19.92 |
| Roi Krakovski | 3 | 29 | 5.58 |
| Maarten Löffler | 4 | 551 | 62.87 |