Geodesic
On Graphs Representable by Pattern-Avoiding Words
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 375-389 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2019},
     volume = {39},
     number = {2},
     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
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
%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/

[1] A.L.L. Gao, S. Kitaev and P.B. Zhang, On 132 -representable graphs, Australas. J. Combin. 69 (2017) 105–118.

[2] M.M. Halldórsson, S. Kitaev and A. Pyatkin, Semi-transitive orientations and word-representable graphs, Discrete Appl. Math. 201 (2016) 164–171. doi:10.1016/j.dam.2015.07.033

[3] S. Kitaev and A. Pyatkin, On representable graphs, J. Autom. Lang. Comb. 13 (2008) 45–54.

[4] S. Heubach and T. Mansour, Combinatorics of Compositions and Words (CRC Press, 2009). doi:10.1201/9781420072686

[5] S. Kitaev, Patterns in Permutations and Words (Springer Science & Business Media, 2011). doi:10.1007/978-3-642-17333-2

[6] S. Kitaev and V. Lozin, Words and Graphs (Springer, NY, 2015). doi:10.1007/978-3-319-25859-1