Word-representability of triangulations of rectangular polyomino with a single domino tile

2015/03/17 by Marc Glen, Glen, Marc, Sergey Kitaev +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1503.05076

To appear in the Journal of Combinatorial Mathematics and Combinatorial Computing

arxiv created 2015/09/09 · arxiv updated 2015/09/11

Abstract

A recent elegant result of Akrobotu et al. states that a triangulation of any convex polyomino is word-representable if and only if it is 3-colorable. In this paper, we generalize a particular case of this result by showing that the result of Akrobotu et al. is true even if we allow a domino tile, instead of having just 1× 1 tiles on a rectangular polyomino.

Related

• Colourability and word-representability of near-triangulations
• On word-representability of polyomino triangulations
• Tiling rectangles with holey polyominoes
• Word-representability of triangulations of grid-covered cylinder graphs
• Rectangular tileability and complementary tileability are undecidable