Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Strathprints

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.

[img] PDF (Akrobotu-etal-SAM-2015-On-word-representability-of-polyomino-triangulations)
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.

Item type: Article
ID code: 51736
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: 21 Sep 2017 12:09
Related URLs:
URI: https://strathprints.strath.ac.uk/id/eprint/51736
Export data:
CORE (COnnecting REpositories)