### Abstract

*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 |
---|---|

Number of pages | 19 |

Journal | Discrete Applied Mathematics |

Publication status | Accepted/In press - 23 May 2016 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*.

}

*Discrete Applied Mathematics*.

**Word-representability of triangulations of grid-covered cylinder graphs.** / Chen, Herman Z.Q.; Kitaev, Sergey; Sun, Brian Y.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Word-representability of triangulations of grid-covered cylinder graphs

AU - Chen, Herman Z.Q.

AU - Kitaev, Sergey

AU - Sun, Brian Y.

PY - 2016/5/23

Y1 - 2016/5/23

N2 - A graph 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 W5 and W7).

AB - A graph 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 W5 and W7).

KW - word-representability

KW - semi-transitive orientation

KW - triangulation

KW - grid-covered

KW - cylinder graph

KW - forbidden induced subgraph

UR - http://www.sciencedirect.com/science/journal/0166218X

M3 - Article

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -