Word-representability of triangulations of rectangular polyomino with a single domino tile

MaRDI QIDQ4977501zbMATH OpenFDO

Authors Marc Glen, Sergey Kitaev

Publication date 16 August 2017

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

zbMATH Keywords

dominopolyominotriangulationword-representability

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A recent elegant result of Akrobotu et al. states that a triangulation of any convex polyomino is word-representable if and only if it is 3-colorable. In this paper, we generalize a particular case of this result by showing that the result of Akrobotu et al. is true even if we allow a domino tile, instead of having just $1imes1$ tiles on a rectangular polyomino.

Recommendations

• On word-representability of polyomino triangulations
• Colourability and word-representability of near-triangulations
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• Word-Representable Graphs: a Survey

Cited in

(6)

• Solving computational problems in the theory of word-representable graphs
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• Word-Representable Graphs: a Survey
• Colourability and word-representability of near-triangulations
• On word-representability of polyomino triangulations

This page was built for publication: Word-representability of triangulations of rectangular polyomino with a single domino tile

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