On word-representability of polyomino triangulations

DOI10.3103/S1055134415010010MaRDI QIDQ894291zbMATH OpenFDO

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

Publication date 30 November 2015

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

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

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)

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.

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

Cites work

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

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
• On semi-transitive orientability of Kneser graphs and their complements
• Colourability and word-representability of near-triangulations
• 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)