Word-Representable Graphs: a Survey

S. V. Kitaev, A. V. Pyatkin

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)278-296
Number of pages19
JournalJournal of Applied and Industrial Mathematics
Volume12
Issue number2
DOIs
Publication statusPublished - 1 Apr 2018

Keywords

  • orientation
  • pattern
  • representation of graphs
  • word

Fingerprint

Dive into the research topics of 'Word-Representable Graphs: a Survey'. Together they form a unique fingerprint.

Cite this