Word-Representable Graphs: a Survey
Sergey Kitaev, A. V. Pyatkin · Journal of Applied and Industrial Mathematics · 2018
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 ∈ 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.