Графы, представимые в виде слов: обзор результатов

Translated title of the contribution: Word-representative graphs: a survey

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticlepeer-review

71 Downloads (Pure)


Letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word xyxy · · · (of even or odd length) or a word yxyx · · · (of even or odd length). A graph G = (V,E) is word-representable if and only if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy ∈ E.
Word-representable graphs generalize several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. This paper is a comprehensive survey on the theory of word-representable graphs and it includes the most recent developments in the area.
Translated title of the contributionWord-representative graphs: a survey
Original languageRussian
Pages (from-to)19-53
Number of pages35
JournalDiskretnyi Analiz i Issledovanie Operatsii
Issue number2
Publication statusPublished - 30 Apr 2018


  • word-representable graphs
  • circle graphs
  • comparability graphs


Dive into the research topics of 'Word-representative graphs: a survey'. Together they form a unique fingerprint.

Cite this