A cubic map is three-colorable iff each interior region is bounded by an even number of regions. A non-cubic map bounded by an even number of regions is not necessarily three-colorable, as evidenced by the tetragonal trapezohedron (dual of the square antiprism), whose faces are all bounded by four other faces but which is not three-colorable (it has chromatic number 4). The Penrose tiles are known to be three-colorable (Babilon 2001).
In general polyform packing problems, the most elegant solutions are cubic and three-colorable. The illustration above shows a three-colorable packing of the 63 unholey (out of 64 total) double-L tetrominoes into a rectangle