## 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$. 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 $K_4$ is word-representable. We make use of semi-transitive orientations to obtain our results.

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 $K_4$ is word-representable. We make use of semi-transitive orientations to obtain our results.

Original language | English |
---|---|

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Siberian Advances in Mathematics |

Volume | 25 |

Issue number | 1 |

DOIs | |

Publication status | Published - 27 Feb 2015 |

## Keywords

- word representability
- semi-transitive orientation
- triangulation
- (convex) polyomino