Word-Representability of Triangulations of Rectangular Polyomino with a Single Domino Tile

Abstract

A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $(x,y)$ is an edge in $E$.

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