Word-representability of triangulations of grid-covered cylinder graphs

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

Research output: Contribution to journalArticle

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

Fingerprint

Representability
Triangulation
Grid
Graph in graph theory
If and only if
Wheels
Sector
Grid Graph
Induced Subgraph
Chromatic number
Alternate
Wheel
Corollary

Keywords

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

Cite this

@article{fca80b0d6db94175a7edb7d05fdb8f39,
title = "Word-representability of triangulations of grid-covered cylinder graphs",
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{\'o}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{\`a}rov{\`a} 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).",
keywords = "word-representability, semi-transitive orientation, triangulation, grid-covered, cylinder graph, forbidden induced subgraph",
author = "Chen, {Herman Z.Q.} and Sergey Kitaev and Sun, {Brian Y.}",
year = "2016",
month = "5",
day = "23",
language = "English",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

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

In: Discrete Applied Mathematics, 23.05.2016.

Research output: Contribution to journalArticle

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

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -