## Abstract

A graph

Akrobotu, Kitaev and Masàrovà 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; indeed, 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

*G=(V,E)*is word-representable if there exists a word*w*over the alphabet*V*such that letters*x*and*y*,*x*≠*y*, alternate in*w*if and only if (*x,y*) ∈*E*. Halldórsson, Kitaev and Pyatkin have shown that a graph is word-representable if and only if it admits a so-called semi-transitive orientation. A corollary of this result is that any 3-colorable graph is word-representable.Akrobotu, Kitaev and Masàrovà 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; indeed, 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}).Original language | English |
---|---|

Pages (from-to) | 60-70 |

Number of pages | 19 |

Journal | Discrete Applied Mathematics |

Volume | 213 |

Publication status | Published - 20 Nov 2016 |

## Keywords

- word-representability
- semi-transitive orientation
- triangulation
- grid-covered
- cylinder graph
- forbidden induced subgraph