Word-representability of triangulations of grid-covered cylinder graphs

DOI10.1016/J.DAM.2016.05.025zbMATH Open1344.05099arXiv1507.06749OpenAlexW2283957606MaRDI QIDQ313795FDOQ313795

Herman Z. Q. Chen, Brian Y. Sun, Sergey Kitaev

Publication date: 12 September 2016

Published in: Discrete Applied 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$, $xeqy$, alternate in $w$ if and only if $(x,y)inE$. Halld'{o}rsson et al. have shown that a graph is word-representable if and only if it admits a so-called semi-transitive orientation. A corollary to this result is that any 3-colorable graph is word-representable. Akrobotu et al. have shown that a triangulation of a grid graph is word-representable if and only if it is 3-colorable. This result does not hold for triangulations of grid-covered cylinder graphs, namely, there are such word-representable graphs with chromatic number 4. In this paper we show that word-representability of triangulations of grid-covered cylinder graphs with three sectors (resp., more than three sectors) is characterized by avoiding a certain set of six minimal induced subgraphs (resp., wheel graphs $W_5$ and $W_7$).

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

zbMATH Keywords

triangulationforbidden induced subgraphgrid-covered cylinder graphsemi-transitive orientationword-representability

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Alternation Graphs
• Word-representability of face subdivisions of triangular grid graphs
• New results on word-representable graphs
• Graphs Capturing Alternations in Words
• Word-representability of triangulations of rectangular polyomino with a single domino tile
• On the Representability of Line Graphs
• Word-Representability of Line Graphs
• On representable graphs
• On word-representability of polyomino triangulations
• Words and graphs
• Semi-transitive orientations and word-representable graphs
• Word problem of the Perkins semigroup via directed acyclic graphs.

Cited In (2)

• Word-Representable Graphs: a Survey
• Solving computational problems in the theory of word-representable graphs

This page was built for publication: Word-representability of triangulations of grid-covered cylinder graphs

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