Word-representable graph: Difference between revisions

Revision as of 06:51, 13 January 2024

Latest revision as of 21:01, 17 June 2025

(4 intermediate revisions by 4 users not shown)

Line 5:

In the mathematical field of [[graph theory]], a '''word-representable graph''' is a [[graph (discrete mathematics)|graph]] that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is ''V'', one should be able to choose a word ''w'' over the alphabet ''V'' such that letters ''a'' and ''b'' alternate in ''w'' if and only if the pair ''ab'' is an edge in the graph. (Letters ''a'' and ''b'' '''alternate''' in ''w'' if, after removing from ''w'' all letters but the copies of ''a'' and ''b'', one obtains a word ''abab''... or a word ''baba''....) For example, the [[cycle graph]] labeled by ''a'', ''b'', ''c'' and ''d'' in clock-wise direction is word-representable because it can be represented by ''abdacdbc'': the pairs ''ab'', ''bc'', ''cd'' and ''ad'' alternate, but the pairs ''ac'' and ''bd'' do not.

The word ''w'' is ''G''<nowiki/>'s ''word-representant'', and one says that that ''w'' ''represents'' ''G''. The smallest (by the number of&nbsp; vertices) non-word-representable graph is the [[wheel graph]] ''W''₅, which is the only non-word-representable graph on 6 vertices.

The definition of a word-representable graph works both in labelled and unlabelled cases since any labelling of a graph is equivalent to any other labelling. Also, the class of word-representable graphs is [[Hereditary property|hereditary]]. Word-representable graphs generalise several important classes of graphs such as [[circle graph]]s, [[Graph coloring|3-colorable graphs]] and [[comparability graph]]s. Various generalisations of the theory of word-representable graphs accommodate representation of ''any'' graph.

Line 11:

==History==

Word-representable graphs were introduced by [[Sergey Kitaev]]<ref>{{cite journal |last1last=Steingrímsson |first1first=Einar |author-link=Einar Steingrímsson|title=The history of the Gothenburg–Reykjavík–Strathclyde Combinatorics Group |journal=Enumerative Combinatorics and Applications |date=2023 |volume=3 |issue=1|pages=Article S1H1 |doi=10.54550/ECA2023V3S1H1|url=http://ecajournal.haifa.ac.il/Volume2023/ECA2023_S1H1.pdf}}</ref> 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.<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> The first systematic study of word-representable graphs was undertaken in a 2008 paper by Kitaev and Artem Pyatkin,<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> 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" /> by Sergey Kitaev and 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 name=":3">[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 name=":4">[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==

Line 123:

# [https://link.springer.com/chapter/10.1007/978-3-030-28796-2_14 M. Gaetz and C. Ji. Enumeration and Extensions of Word-representants, Combinatorics on words, 180-192, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019.]

# [[arxiv:1602.08965|A. Gao, S. Kitaev, and P. Zhang. On 132-representable graphs. Australasian J. Combin. 69 (2017), 105−118.]]

# [[arxiv:1605.01688|M. E. Glen. Colourability and word-representability of near-triangulations, Pure andMathematics Appliedand MathematicsApplications, to appear28(1), 2019, 70−76.]]

# M. E. Glen. On word-representability of polyomino triangulations & crown graphs, 2019. PhD thesis, University of Strathclyde.

# [[arxiv:1503.05076|M. E. Glen and S. Kitaev. Word-Representability of Triangulations of Rectangular Polyomino with a Single Domino Tile, J. Combin.Math. Combin. Comput. 100, 131−144, 2017.]]

# [https://www.sciencedirect.com/science/article/pii/S0166218X18301045 M. E. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph, Discr. Appl. Math. 244, 2018, 89−93.]

# [https://arxiv.org/abs/0810.0310 M.M. Halldórsson, S. Kitaev, A. Pyatkin On representable graphs, semi-transitive orientations, and the representation numbers, arXiv:0810.0310 (2008).]

# [https://web.archive.org/web/20190302114930/http://pdfs.semanticscholar.org/a2df/a4c88505510ea1a7d4357972d9ab24575195.pdf 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.]

Line 151:

Software to study word-representable graphs can be found here:

#[http://personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.html M. E. Glen. Software to deal with word-representable graphs, 2017. Available at https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html.]

# [https://www.win.tue.nl/~hzantema/reprnr.html H. Zantema. Software REPRNR to compute the representation number of a graph, 2018. Available at https://www.win.tue.nl/~hzantema/reprnr.html.]

Line 161:

[[Category:Graph families]]

[[Category:NP-complete problems]]