On 132-representable graphs

Gao, Alice L.L. and Kitaev, Sergey and Zhang, Philip B. (2017) On 132-representable graphs. Australasian Journal of Combinatorics, 69 (1). pp. 105-118. ISSN 1034-4942 (In Press)

[thumbnail of Gao-etal-AJC2017-On-132-representable-graphs]
Preview
 Text. Filename: Gao_etal_AJC2017_On_132_representable_graphs.pdf
Accepted Author Manuscript
Download (120kB)| 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 alternate in w if and only if xy is an edge in E. Word-representable graphs are the subject of a long research line in the literature, and they are the main focus in the recently published book "Words and Graphs" by Kitaev and Lozin. A word w = w1...wn avoids the pattern 132 if there are no 1 ≤ i1 < i2 < i3 ≤ n such that wi1 < wi3 < wi2. The theory of patterns in words and permutations is a fast growing area. A recently suggested research direction is in merging the theories of word-representable graphs and patterns in words. Namely, given a class of pattern-avoiding words, can we describe the class of graphs represented by the words? We say that a graph is 132-representable if it can be represented by a 132-avoiding word. We show that each 132-representable graph is necessarily a circle graph. Also, we show that any tree and any cycle graph are 132-representable. Finally, we provide explicit 132-avoiding representations for all graphs on at most five vertices, and also describe all such representations, and enumerate them, for complete graphs.

CORE (COnnecting REpositories)