Word-representability of triangulations of grid-covered cylinder graphs

作者：Chen, Herman Z. Q.; Kitaev, Sergey; Sun, Brian Y.^*

来源：Discrete Applied Mathematics, 2016, 213: 60-70.

DOI：10.1016/j.dam.2016.05.025

• Word-representability
• Semi-transitive orientation
• Triangulation
• Grid-covered cylinder graph
• Forbidden induced subgraph

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 not equal y, alternate in w if and only if (x, y) is an element of E. Halldorsson, 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 Masarova 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).

• 出版日期2016-11-20
• 单位天津城建大学; 新疆大学