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

Kitaev, Sergey and Pyatkin, Artem (2018) Графы, представимые в виде слов : обзор результатов. Diskretnyi Analiz i Issledovanie Operatsii, 25 (2). pp. 19-53. ISSN 1990-4797 (https://doi.org/10.17377/daio.2018.25.588)

[thumbnail of Kitaev-Pyatkin-DAIO2017-Word-representative-graphs-a-survey]
Preview
 Text. Filename: Kitaev_Pyatkin_DAIO2017_Word_representative_graphs_a_survey.pdf
Accepted Author Manuscript
Download (836kB)| Preview

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
  • Item type:Article
    ID code:62535
    Dates:
    Date
    Event
    30 April 2018
    Published
    30 November 2017
    Accepted
    Keywords:word-representable graphs, circle graphs, comparability graphs, Mathematics, Computational Mathematics
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:06 Dec 2017 11:35
    Last modified:25 Mar 2022 01:51
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/62535
CORE (COnnecting REpositories)