On word-representability of polyomino triangulations

P. Akrobotu, S. Kitaev, Z. Masarova

Research output: Contribution to journalArticle

7 Citations (Scopus)

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.
LanguageEnglish
Pages1-10
Number of pages10
JournalSiberian Advances in Mathematics
Volume25
Issue number1
DOIs
Publication statusPublished - 27 Feb 2015

Fingerprint

Polyomino
Representability
Triangulation
Graph in graph theory
If and only if
Complete Graph
Alternate
Cycle
Arbitrary

Keywords

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

Cite this

Akrobotu, P. ; Kitaev, S. ; Masarova, Z. / On word-representability of polyomino triangulations. In: Siberian Advances in Mathematics. 2015 ; Vol. 25, No. 1. pp. 1-10.
@article{b3edf2092a524c25ad693f20157d0697,
title = "On word-representability of polyomino triangulations",
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.",
keywords = "word representability, semi-transitive orientation, triangulation, (convex) polyomino",
author = "P. Akrobotu and S. Kitaev and Z. Masarova",
year = "2015",
month = "2",
day = "27",
doi = "10.3103/S1055134415010010",
language = "English",
volume = "25",
pages = "1--10",
journal = "Siberian Advances in Mathematics",
issn = "1055-1344",
publisher = "Springer",
number = "1",

}

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

In: Siberian Advances in Mathematics, Vol. 25, No. 1, 27.02.2015, p. 1-10.

Research output: Contribution to journalArticle

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 -