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)
|
Text (Kitaev-DLT-2017-A-comprehensive-introduction-to-the-theory-of-word-representable-graphs)
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.
Creators(s): |
Kitaev, Sergey ![]() | Item type: | Book Section |
---|---|
ID code: | 60730 |
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: | 06 Mar 2021 02:58 |
Related URLs: | |
URI: | https://strathprints.strath.ac.uk/id/eprint/60730 |
Export data: |