A comprehensive introduction to the theory of word-representable graphs

Kitaev, Sergey; (2017) A comprehensive introduction to the theory of word-representable graphs. In: Developments in Language Theory. Lecture Notes in Computer Science . Springer-Verlag, BEL. (In Press)

[thumbnail of Kitaev-DLT-2017-A-comprehensive-introduction-to-the-theory-of-word-representable-graphs]
Preview
 Text. Filename: Kitaev_DLT_2017_A_comprehensive_introduction_to_the_theory_of_word_representable_graphs.pdf
Accepted Author Manuscript
Download (577kB)| 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 offers a comprehensive introduction to the theory of word-representable graphs including the most recent developments in the area.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
  • Item type:Book Section
    ID code:60730
    Dates:
    Date
    Event
    17 May 2017
    Published
    17 May 2017
    Accepted
    Notes:The final publication will be available at link.springer.com
    Keywords:word-representable graphs, pattern avoiding words, semi-trasitive orientations, non-word representable graphs, operations, edge subdivision, edge contraction, cartesian products, planar graphs, Mathematics, Mathematics(all)
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:19 May 2017 15:49
    Last modified:20 Jul 2022 00:51
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/60730
CORE (COnnecting REpositories)