Word-representative graphs: a survey

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

Abstract

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
LanguageRussian
Pages19-53
Number of pages35
JournalDiskretnyi Analiz i Issledovanie Operatsii
Volume25
Issue number2
DOIs
StatePublished - 30 Apr 2018

Fingerprint

Graph in graph theory
Alternate
Odd
Circle Graph
If and only if
Comparability Graph
Generalise
Class

Keywords

  • word-representable graphs
  • circle graphs
  • comparability graphs

Cite this

@article{c6a989d598334cf78f39e61f14d00b02,
title = "Графы, представимые в виде слов: обзор результатов",
abstract = "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.",
keywords = "word-representable graphs, circle graphs, comparability graphs",
author = "Sergey Kitaev and Artem Pyatkin",
year = "2018",
month = "4",
day = "30",
doi = "10.17377/daio.2018.25.588",
language = "Russian",
volume = "25",
pages = "19--53",
journal = "Diskretnyi Analiz i Issledovanie Operatsii",
issn = "1990-4789",
number = "2",

}

Графы, представимые в виде слов : обзор результатов. / Kitaev, Sergey; Pyatkin, Artem.

In: Diskretnyi Analiz i Issledovanie Operatsii, Vol. 25, No. 2, 30.04.2018, p. 19-53.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Графы, представимые в виде слов

T2 - Diskretnyi Analiz i Issledovanie Operatsii

AU - Kitaev,Sergey

AU - Pyatkin,Artem

PY - 2018/4/30

Y1 - 2018/4/30

N2 - 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.

AB - 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.

KW - word-representable graphs

KW - circle graphs

KW - comparability graphs

UR - http://www.mathnet.ru/php/journal.phtml?jrnid=da&option_lang=eng

U2 - 10.17377/daio.2018.25.588

DO - 10.17377/daio.2018.25.588

M3 - Article

VL - 25

SP - 19

EP - 53

JO - Diskretnyi Analiz i Issledovanie Operatsii

JF - Diskretnyi Analiz i Issledovanie Operatsii

SN - 1990-4789

IS - 2

ER -