On the Computation and Chromatic Number of Colored Domino Tilings.
Chris Worman, Boting Yang · Canadian Conference on Computational Geometry · 2005
A colored domino is a rotatable 2× 1 rectangle that is partitioned into two unit squares, which are called faces, each of which is assigned a color. In a colored domino tiling of an orthogonal polygon P , a set of dominoes completely covers P such that no dominoes overlap and so that adjacent faces have the same color. We provide tight bounds on the number of colors required to tile simple and non-simple orthogonal polygons. We also present an algorithm for computing a colored domino tiling of a simple orthogonal polygon.