### Abstract

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.

Language | English |
---|---|

Pages | 1-10 |

Number of pages | 10 |

Journal | Siberian Advances in Mathematics |

Volume | 25 |

Issue number | 1 |

DOIs | |

Publication status | Published - 27 Feb 2015 |

### Fingerprint

### Keywords

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

### Cite this

*Siberian Advances in Mathematics*,

*25*(1), 1-10. https://doi.org/10.3103/S1055134415010010

}

*Siberian Advances in Mathematics*, vol. 25, no. 1, pp. 1-10. https://doi.org/10.3103/S1055134415010010

**On word-representability of polyomino triangulations.** / Akrobotu, P.; Kitaev, S.; Masarova, Z.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On word-representability of polyomino triangulations

AU - Akrobotu, P.

AU - Kitaev, S.

AU - Masarova, Z.

PY - 2015/2/27

Y1 - 2015/2/27

N2 - 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.

AB - 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.

KW - word representability

KW - semi-transitive orientation

KW - triangulation

KW - (convex) polyomino

UR - http://arxiv.org/abs/1405.3527

UR - http://www.springer.com/mathematics/journal/12002

U2 - 10.3103/S1055134415010010

DO - 10.3103/S1055134415010010

M3 - Article

VL - 25

SP - 1

EP - 10

JO - Siberian Advances in Mathematics

T2 - Siberian Advances in Mathematics

JF - Siberian Advances in Mathematics

SN - 1055-1344

IS - 1

ER -