Word-representable graph: Difference between revisions

Revision as of 09:30, 5 February 2020

Revision as of 09:34, 5 February 2020

Line 17:

==History==

Sergey Kitaev introduced the theory of word-representable graphs in 2004 based on joint research with Steven Seif <ref name="KS08">S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008), 177−194.</ref> on the ''Perkins semigroup'', which has played an important role in semigroup theory since 1960. However, the first systematic study of word-representable graphs was not undertaken until the 2008 paper <ref name="KP08">[https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/repgr.pdf S. Kitaev and A. Pyatkin. On representable graphs, J. Autom., Lang. and Combin. 13 (2008), 45−54.]</ref> by Sergey Kitaev and Artem Pyatkin starting development of the theory. One of key contributors to the area is [http://www.ru.is/~mmh/ Magnús M. Halldórsson] <ref name=":0">[https://link.springer.com/chapter/10.1007/978-3-642-14455-4_41 M.M. Halldórsson, S. Kitaev, A. Pyatkin (2010) Graphs capturing alternations in words. In: Y. Gao, H. Lu, S. Seki, S. Yu (eds), Developments in Language Theory. DLT 2010. Lecture Notes Comp. Sci. 6224, Springer, 436−437.]</ref> <ref name=":1">[https://link.springer.com/chapter/10.1007/978-3-642-25870-1_18 M.M. Halldórsson, S. Kitaev, A. Pyatkin (2011) Alternation graphs. In: P. Kolman, J. Kratochvíl (eds), Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes Comp. Sci. 6986, Springer, 191−202.]</ref> <ref name="HKP16">[https://www.sciencedirect.com/science/article/pii/S0166218X15003868 M. Halldórsson, S. Kitaev and A. Pyatkin. Semi-transitive orientations and word-representable graphs, Discr. Appl. Math. 201 (2016), 164−171.]</ref>. Up to date, 35+ papers have been written on the subject, and the core of the book <ref name="KL15">[https://www.springer.com/la/book/9783319258577 S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015.] {{ISBN|978-3-319-25859-1}}</ref> by [https://personal.cis.strath.ac.uk/sergey.kitaev/ Sergey Kitaev] and [http://homepages.warwick.ac.uk/~masgax/ Vadim Lozin] is devoted to the theory of word-representable graphs. A quick way to get familiar with the area is to read one of the survey articles <ref name=":2">[[arxiv:1705.05924|S. Kitaev. A comprehensive introduction to the theory of word-representable graphs.]] In: É. Charlier, J. Leroy, M. Rigo (eds), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.</ref> <ref>[https://link.springer.com/article/10.1134/S1990478918020084 S. Kitaev and A. Pyatkin. Word-representable graphs: a Survey, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.]</ref> <ref>[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=da&paperid=894&option_lang=rus С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25,номер 2, 19−53]</ref>.

==Motivation to study the graphs==