On word-representability of polyomino triangulations

2014/05/14 by Prosper D. Akrobotu, Akrobotu, Prosper, Sergey Kitaev +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1405.3527

openalex publication_date 2014/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 is showing that a triangulation of any convex polyomino is word-representable if and only if it is 3-colorable. We demonstrate 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₄ is word-representable. We employ semi-transitive orientations to obtain our results.

Cited by

• Line Graphs of Non-Word-Representable Graphs are Not Always Non-Word-Representable

Related

• Colourability and word-representability of near-triangulations
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of triangulations of rectangular polyomino with a single domino tile
• Word-representability of subdivisions of triangular grid graphs
• Semi-Transitive Orientations and Word-Representable Graphs