Графы, представимые в виде слов : обзор результатов
Kitaev, Sergey and Pyatkin, Artem (2018) Графы, представимые в виде слов : обзор результатов. Diskretnyi Analiz i Issledovanie Operatsii, 25 (2). pp. 19-53. ISSN 1990-4797
|
Text (Kitaev-Pyatkin-DAIO2017-Word-representative-graphs-a-survey)
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.
Creators(s): |
Kitaev, Sergey ![]() | Item type: | Article |
---|---|
ID code: | 62535 |
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: | 21 Jan 2021 09:43 |
Related URLs: | |
URI: | https://strathprints.strath.ac.uk/id/eprint/62535 |
Export data: |