Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Word-Representable Graphs : a Survey. / Kitaev, S. V.; Pyatkin, A. V.
в: Journal of Applied and Industrial Mathematics, Том 12, № 2, 01.04.2018, стр. 278-296.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Word-Representable Graphs
T2 - a Survey
AU - Kitaev, S. V.
AU - Pyatkin, A. V.
PY - 2018/4/1
Y1 - 2018/4/1
N2 - 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.
AB - 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.
KW - orientation
KW - pattern
KW - representation of graphs
KW - word
UR - http://www.scopus.com/inward/record.url?scp=85047875062&partnerID=8YFLogxK
U2 - 10.1134/S1990478918020084
DO - 10.1134/S1990478918020084
M3 - Article
AN - SCOPUS:85047875062
VL - 12
SP - 278
EP - 296
JO - Journal of Applied and Industrial Mathematics
JF - Journal of Applied and Industrial Mathematics
SN - 1990-4789
IS - 2
ER -
ID: 13755447