Geodesic
On Graphs Representable by Pattern-Avoiding Words
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 375-389

Voir la notice de l'article provenant de la source Library of Science

In this paper we study graphs defined by pattern-avoiding words. Word-representable graphs have been studied extensively following their introduction in 2004 and are the subject of a book published by Kitaev and Lozin in 2015. Recently there has been interest in studying graphs represented by pattern-avoiding words. In particular, in 2016, Gao, Kitaev, and Zhang investigated 132-representable graphs, that is, word-representable graphs that can be represented by a word which avoids the pattern 132. They proved that all 132-representable graphs are circle graphs and provided examples and properties of 132-representable graphs. They posed several questions, some of which we answer in this paper. One of our main results is that not all circle graphs are 132-representable, thus proving that 132-representable graphs are a proper subset of circle graphs, a question that was left open in the paper by Gao et al. We show that 123-representable graphs are also a proper subset of circle graphs, and are different from 132-representable graphs. We also study graphs represented by pattern-avoiding 2-uniform words, that is, words in which every letter appears exactly twice.
Keywords: pattern-avoidance, word-representability, circle graphs 
@article{DMGT_2019_39_2_a6,
     author = {Mandelshtam, Yelena},
     title = {On {Graphs} {Representable} by {Pattern-Avoiding} {Words}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {375--389},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a6/}
}
TY  - JOUR
AU  - Mandelshtam, Yelena
TI  - On Graphs Representable by Pattern-Avoiding Words
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 375
EP  - 389
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a6/
LA  - en
ID  - DMGT_2019_39_2_a6
ER  - 
%0 Journal Article
%A Mandelshtam, Yelena
%T On Graphs Representable by Pattern-Avoiding Words
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 375-389
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a6/
%G en
%F DMGT_2019_39_2_a6
Mandelshtam, Yelena. On Graphs Representable by Pattern-Avoiding Words. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 375-389. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a6/