## 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 = w

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.

_{1}...w_{n}avoids the pattern 132 if there are no 1 ≤ i_{1}< i_{2}< i_{3}≤ n such that w_{i1}< w_{i3}< w_{i2}. 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.

Original language | English |
---|---|

Pages (from-to) | 105-118 |

Journal | Australasian Journal of Combinatorics |

Volume | 69 |

Issue number | 1 |

Publication status | Accepted/In press - 19 Jul 2017 |

## Keywords

- word-representable graph
- pattern-avoiding word
- circle graph
- tree
- complete graph
- cycle graph