On 132-representable graphs

Tools

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.

ORCID iDs

Gao, Alice L.L., Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zhang, Philip B.;
CORE (COnnecting REpositories)