Word-representable graph: Difference between revisions

Revision as of 19:51, 20 August 2023

Latest revision as of 21:01, 17 June 2025

(7 intermediate revisions by 6 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 |last=Steingrímsson |first=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 83:

==Generalisations==

A number of generalisations <ref name="JKPR2015">[https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p53 M. Jones, S. Kitaev, A. Pyatkin, and J. Remmel. Representing Graphs via Pattern Avoiding Words, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).]</ref><ref name="GJ2019">[https://www.lehmanns.de/shop/mathematik-informatik/48968161-9783030287955-combinatorics-on-words M. Gaetz and C. Ji. Enumeration and extensions of word-representable graphs. Lecture Notes in Computer Science 11682 (2019) 180−192. In R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. WORDS 2019.]</ref><ref name="GJ2019-2">[[arXiv:1909.00019|M. Gaetz and C. Ji. Enumeration and Extensions of Word-representants, arXiv:1909.00019.]]</ref> of the notion of a word-representable graph are based on the observation by [https://www[Jeffrey B.math.ucsd.edu/memorials/jeffrey-remmel/ Remmel|Jeff Remmel]] that non-edges are defined by occurrences of the pattern 11 (two consecutive equal letters) in a word representing a graph, while edges are defined by avoidance of this pattern. For example, instead of the pattern 11, one can use the pattern 112, or the pattern, 1212, or any other binary pattern where the assumption that the alphabet is ordered can be made so that a letter in a word corresponding to 1 in the pattern is less than that corresponding to 2 in the pattern. Letting ''u'' be an ordered binary pattern we thus get the notion of a '''''u''-representable graph'''. So, word-representable graphs are just the class of 11-representable graphs. Intriguingly, '''any graph''' can be ''u''-represented assuming ''u'' is of length at least 3.<ref name="K2017">[https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22097 S. Kitaev. Existence of u-representation of graphs, Journal of Graph Theory 85 (2017) 3, 661−668.]</ref>

Another way to generalise the notion of a word-representable graph, again suggested by [https://www.math.ucsd.edu/memorials/jeffrey-remmel/ Jeff Remmel], is to introduce the "degree of tolerance" ''k'' for occurrences of a pattern ''p'' defining edges/non-edges. That is, we can say that if there are up to ''k'' occurrence of ''p'' formed by letters ''a'' and ''b'', then there is an edge between ''a'' and ''b''. This gives the notion of a ''k''-''p''-representable graph, and ''k''-11-representable graphs are studied in.<ref name="CKKK2019">[[arxiv:1803.01055|G.-S. Cheon, J. Kim, M. Kim, and A. Pyatkin. On ''k''-11-representable graphs. J. Combin. 10 (2019) 3, 491−513.]]</ref> Note that 0-11-representable graphs are precisely word-representable graphs. The key results in <ref name="CKKK2019" /> are that '''any''' graph is 2-11-representable and that word-representable graphs are a proper subclass of 1-11-representable graphs. Whether or not any graph is 1-11-representable is a challenging open problem.

For yet another type of relevant generalisation, [[Hans Zantema]] suggested the notion of a '''''k''-semi-transitive orientation''' refining the notion of a semi-transitive orientation.<ref name="AGKZ2019" /> The idea here is restricting ourselves to considering ''only'' directed paths of length not exceeding ''k'' while allowing violations of semi-transitivity on longer paths.

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]]