2015/07/24 by Chen, Thomas Z. Q., Kitaev, Sergey, Sun, Brian Y.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1507.06749
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 et al. have shown that a graph is word-representable if and only if it admits a so-called semi-transitive orientation. A corollary to this result is that any 3-colorable graph is word-representable. Akrobotu et al. 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, namely, 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).