On Word-Representability of Polyomino Triangulations

摘要

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. Some graphs are word-representable, others are not. It is known that a graph is word-representable if and only if it accepts a so-called semi-transitive orientation. The main result of this paper states that a triangulation of any convex polyomino is word-representable if and only if it is 3-colorable. On the other hand, we provide an example showing that this statement is not true for an arbitrary polyomino. We also show that the graph obtained by replacing each 4-cycle in a polyomino by the complete graph K4 is word-representable. We make use of semi-transitive orientations to obtain our results.