Word-representable graphs: a survey

Letters $x$ and $y$ alternate in a word $w$ if after deleting all letters but $x$ and $y$ in $w$ we get either a word $xyxy…$ or a word $yxyx…$ (each of these words can be of odd or even length). A graph $G=(V,E)$ is word-representable if there is a finite word $w$ over an alphabet $V$ such that the letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. The word-representable graphs include many important graph classes, in particular, circle graphs, $3$-colorable graphs and comparability graphs. In this paper we present the full survey of the available results on the theory of word-representable graphs and the most recent achievements in this field. Tab. 2, illustr. 11, bibliogr. 48.