On word-representability of polyomino triangulations

DOI10.3103/S1055134415010010zbMATH Open1326.05028arXiv1405.3527MaRDI QIDQ894291FDOQ894291

Authors: P. Akrobotu, Sergey Kitaev, Zuzana Masárová 

Publication date: 30 November 2015

Published in: Siberian Advances in Mathematics (Search for Journal in Brave)

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_4$ is word-representable. We employ semi-transitive orientations to obtain our results.

Full work available at URL: https://arxiv.org/abs/1405.3527

Recommendations

• Word-representability of triangulations of rectangular polyomino with a single domino tile
• Colourability and word-representability of near-triangulations
• Word-representability of triangulations of grid-covered cylinder graphs
• Semi-transitive orientations and word-representable graphs
• Word-representability of split graphs

zbMATH Keywords

triangulationsemi-transitive orientationword-representability(convex) polyomino

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Polyominoes (05B50)

Cites Work

• Every planar map is four colorable. I: Discharging
• Alternation graphs
• New results on word-representable graphs
• Graphs Capturing Alternations in Words
• On the Representability of Line Graphs
• Word-representability of line graphs
• On representable graphs
• Words and graphs
• On graphs with representation number 3

Cited In (9)

• Word-representability of triangulations of rectangular polyomino with a single domino tile
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• Word-Representable Graphs: a Survey
• Semi-transitive orientations and word-representable graphs
• Representing graphs via pattern avoiding words
• Colourability and word-representability of near-triangulations
• On semi-transitive orientability of Kneser graphs and their complements
• Solving computational problems in the theory of word-representable graphs

This page was built for publication: On word-representability of polyomino triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894291)