Word-representability of triangulations of grid-covered cylinder graphs
Chen, Herman Z.Q. and Kitaev, Sergey and Sun, Brian Y. (2016) Word-representability of triangulations of grid-covered cylinder graphs. Discrete Applied Mathematics, 213. pp. 60-70. ISSN 0166-218X
Preview |
Text.
Filename: Chen_etal_DAM2016_Word_representability_of_triangulations_of_grid_covered_cylinder_graphs.pdf
Accepted Author Manuscript License: Download (237kB)| Preview |
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, 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).
ORCID iDs
Chen, Herman Z.Q., Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Sun, Brian Y.;-
-
Item type: Article ID code: 56490 Dates: DateEvent20 November 2016Published23 May 2016AcceptedSubjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 24 May 2016 10:23 Last modified: 22 Sep 2024 00:50 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/56490