Polychromatic colorings of rectangular partitions
Polychromatic colorings of rectangular partitions
复制标题
矩形隔断的多色着色
DOI：
10.1016/j.disc.2008.07.035
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Roi Krakovski
中科院分区：
文献类型：
--
作者：
D. Dimitrov;Elad Horev;Roi Krakovski
矩形划分是将一个平面矩形划分成任意数量的互不重叠的矩形，使得没有四个矩形共享一个角。证明了每个矩形划分都有四种颜色的顶点着色，使得每个矩形(可能外矩形除外)在其边界上都有四种颜色。这解决了Dinitz等人的一个猜想。[Y.Dinitz，M.J.Katz，R.Krakovski，Guarding矩形隔断，见：摘要第23期欧洲。车间计算。Geom.，2007，第30-33页]。证明是简短的，并且基于一类特定平面图的4-边可染性。
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.