Word-representability of triangulations of grid-covered cylinder graphs

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

Research output: Contribution to journalArticle

18 Downloads (Pure)

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, xy, 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).
Original languageEnglish
Number of pages19
JournalDiscrete Applied Mathematics
Publication statusAccepted/In press - 23 May 2016

Keywords

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

Fingerprint Dive into the research topics of 'Word-representability of triangulations of grid-covered cylinder graphs'. Together they form a unique fingerprint.

Cite this