On word-representability of polyomino triangulations

Akrobotu, P. and Kitaev, S. and Masarova, Z. (2015) On word-representability of polyomino triangulations. Siberian Advances in Mathematics, 25 (1). pp. 1-10. ISSN 1934-8126 (https://doi.org/10.3103/S1055134415010010)

[thumbnail of Akrobotu-etal-SAM-2015-On-word-representability-of-polyomino-triangulations] PDF. Filename: Akrobotu_etal_SAM_2015_On_word_representability_of_polyomino_triangulations.pdf
Accepted Author Manuscript
Download (111kB)

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.

ORCID iDs

Akrobotu, P., Kitaev, S. ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Masarova, Z.;
  • Item type:Article
    ID code:51736
    Dates:
    Date
    Event
    27 February 2015
    Published
    26 September 2014
    Accepted
    Keywords:word representability, semi-transitive orientation, triangulation, (convex) polyomino, Mathematics, Mathematics(all)
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:18 Feb 2015 10:14
    Last modified:23 Sep 2021 04:53
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/51736
CORE (COnnecting REpositories)