Word-representable graph: Difference between revisions

Revision as of 16:57, 24 April 2020

Latest revision as of 21:01, 17 June 2025

(19 intermediate revisions by 16 users not shown)

Line 1:

{{Technical|date=April 2020}}

<!-- Note: The following pages were redirects to [[Word-representable_graph]] before draftification:

*[[Draft:Word-representable graphs]]

Line 6 ⟶ 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 [[Circlecircle graph|circle graphs]]s, [[Graph coloring|3-colorable graphs]] and [[Comparabilitycomparability graph|comparability graphs]]s. Various generalisations of the theory of word-representable graphs accommodate representation of ''any'' graph.

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

According to ,<ref name="KL15" />, word-representable graphs are relevant to various fields, thus providing a motivationmotivating to study the graphs. These fields are [[algebra]], [[graph theory]], [[computer science]], [[combinatorics on words]], and [[scheduling]]. Word-representable graphs are especially important in graph theory, since they generalise several important classes of graphs, e.g. [[Circlecircle graph|circle graphs]]s, [[Graph coloring|3-colorable graphs]] and [[Comparabilitycomparability graph|comparability graphs]]s.

==Early results==

It was shown in <ref name="KP08" /> that a graph ''G'' is word-representable iffif it is '''k-representable''' for some ''k'', that is, ''G'' can be represented by a word having ''k'' copies of each letter. Moreover, if a graph is ''k''-representable then it is also (''k''&nbsp;+&nbsp;1)-representable. Thus, the notion of the '''representation number of a graph''', as the ''minimum'' ''k'' such that a graph is word-representable, is well-defined. Non-word-representable graphs have the representation number ∞. Graphs with representation number 1 are precisely the set of [[Completecomplete graph|complete graphs]]s, while graphs with representation number 2 are precisely the class of [[Circle graph|circle]] non-complete graphs. In particular, [http://mathworld.wolfram.com/Forest.html forests] (except for single [[Tree (graph theory)|trees]] on at most 2 vertices), [[Ladderladder graph|ladder graphs]]s and [[Cyclecycle graph|cycle graphs]]s have representation number 2. No classification for graphs with representation number 3 is known. However, there are examples of such graphs, e.g. [[Petersen graph|Petersen's graph]] and [http://mathworld.wolfram.com/PrismGraph.html prisms]. Moreover, the 3-[[Homeomorphism (graph theory)|subdivision]] of any graph is 3-representable. In particular, for every graph ''G'' there exists a 3-representable graph ''H'' that contains ''G'' as a [[Graph minor|minor]] .<ref name="KP08" />.

A graph ''G'' is '''permutationally representable''' if it can be represented by a word of the form ''p''₁''p''₂...''p_k'', where ''p_i'' is a [[permutation]]. On can also say that ''G'' is '''permutationally ''k''-representable'''. A graph is permutationally representable iff it is a [[Comparability graph|comparability graph]] .<ref name="KS08" />. A graph is word-representable implies that the [[Neighbourhood (graph theory)|neighbourhood]] of each vertex is permutationally representable (i.e. is a [[comparability graph]]) .<ref name="KS08" />. Converse to the last statement is not true .<ref name=":0" />. However, the fact that the [[Neighbourhood (graph theory)|neighbourhood]] of each vertex is a [[comparability graph]] implies that the [[Clique problem|Maximum Clique problem]] is polynomially solvable on word-representable graphs .<ref name=":1" /> <ref name="HKP16" />.

==Semi-transitive orientations==

Semi-transitive orientations provide a powerful tool to study word-representable graphs. A directed graph is '''semi-transitively oriented''' iff it is [http://mathworld.wolfram.com/AcyclicGraph.html acyclic] and for any directed path ''u''₁→''u''₂→ ...→''u_t'', ''t'' ≥ 2, either there is no edge from ''u''₁ to ''u_t'' or all edges ''u_i'' → ''u_j'' exist for 1 ≤ ''i'' < ''j'' ≤ ''t''. A key theorem in the theory of word-representable graphs states that a graph is word-representable iff it admits a semi-transitive orientation .<ref name="HKP16" />. As a corollary to the proof of the key theorem one obtain an upper bound on word-representants: Each non-complete word-representable graph ''G'' is 2(''n''&nbsp;−&nbsp;''κ''(''G''))-representable, where ''κ''(''G'') is the size of a maximal clique in ''G'' .<ref name="HKP16" />. As an immediate corollary of the last statement, one has that the [https://www.encyclopediaofmath.org/index.php/Recognition_problem recognition problem] of word-representability is in [[NP (complexity)|NP]]. In 2014, [http://fc.isima.fr/~limouzy/ Vincent Limouzy] observed that it is an [[NP-completeness|NP-complete problem]] to recognise whether a given graph is word-representable .<ref name="KL15" /> <ref name=":2" />. Another important corollary to the key theorem is that any [[Graph coloring|3-colorable graph]] is word-representable. The last fact implies that many classical graph problems are NP-hard on word-representable graphs.  

==Overview of selected results==

Line 32 ⟶ 31:

===Non-word-representable graphs===

[[Wheel graph|Wheel graphs]]s ''W''_2''n''+1, for ''n'' ≥ 2, are not word-representable and ''W''₅ is the minimum (by the number of vertices) non-word-representable graph. Taking any non-comparability graph and adding an apex (a vertex connected to any other vertex), we obtain a non-word-representable graph, which then can produce infinitely many non-word-representable graphs .<ref name="KL15" />. Any graph produced in this way will necessarily have a triangle (a cycle of length 3), and a vertex of degree at least 5. Non-word-representable graphs of maximum degree 4 exist <ref>[[arxiv:1307.1810|A. Collins, S. Kitaev, and V. Lozin. New results on word-representable graphs, Discr. Appl. Math. 216 (2017), 136–141.]]</ref> and non-word-representable triangle-free graphs exist .<ref name=":1" />. Regular non-word representable graphs also exist .<ref name="KL15" />. Non-isomorphic non-word-representable connected graphs on at most eight vertices were first enumerated by Heman Z.Q. Chen. His calculations were extended in ,<ref>[https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/kitaev11.html Ö. Akgün, I.P. Gent, S. Kitaev, H. Zantema. Solving computational problems in the theory of word-representable graphs. Journal of Integer Sequences 22 (2019), Article 19.2.5.]

</ref>, where it was shown that the numbers of non-isomorphic non-word-representable connected graphs on 5−11 vertices are given, respectively, by 0, 1, 25, 929, 54957, 4880093, 650856040. This is the sequence A290814 in the [http://oeis.org/search?q=1%2C+25%2C+929%2C+54957%2C+4880093&language=english&go=Search Online Encyclopaedia of Integer Sequences (OEIS)].

===Operations on graphs and word-representability===

Operations preserving word-representability are removing a vertex, replacing a vertex with a module, Cartesian product, rooted product, subdivision of a graph, connecting two graphs by an edge and gluing two graphs in a vertex .<ref name="KL15" />. The operations not necessarily preserving word-representability are taking the complement, taking the line graph, edge contraction ,<ref name="KL15" />, gluing two graphs in a clique of size 2 or more ,<ref name="CKS2019" />, tensor product, lexicographic product and strong product .<ref name="CKK2019">[https://link.springer.com/content/pdf/10.1007/s10878-018-0358-7.pdf I. Choi, J. Kim, and M. Kim. On operations preserving semi-transitive orient ability of graphs, Journal of Combinatorial Optimization 37 (2019) 4, 1351−1366.]</ref>. Edge-deletion, edge-addition and edge-lifting with respect to word-representability (equivalently, semi-transitive orientability) are studied in .<ref name="CKK2019" />.

===Graphs with high representation number===

While each non-complete word-representable graph ''G'' is 2(''n''&nbsp;−&nbsp;''κ''(''G''))-representable, where ''κ''(''G'') is the size of a maximal clique in ''G'' ,<ref name="HKP16" />, the highest known representation number is floor(''n''/2) given by [[Crowncrown graph|crown graphs]]s with an all-adjacent vertex .<ref name="HKP16" />. Interestingly, such graphs are not the only graphs that require long representations .<ref name="AGKZ2019">[https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/kitaev11.pdf Ö. Akgün, I.P. Gent, S. Kitaev, H. Zantema. Solving computational problems in the theory of word-representable graphs. Journal of Integer Sequences 22 (2019), Article 19.2.5.]</ref>. Crown graphs themselves are shown to require long (possibly longest) representations among bipartite graphs .<ref name="GKP18">[https://www.sciencedirect.com/science/article/pii/S0166218X18301045 M. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph, Discr. Appl. Math. 244, 2018, 89–93.]</ref>.

===Computational complexity===

Known computational complexities for problems on word-representable graphs can be summarised as follows :<ref name="KL15" /> <ref name=":2" />:

{| class="wikitable"

Line 72 ⟶ 71:

===Representation of planar graphs===

Triangle-free [[planar graphs]] are word-representable .<ref name="HKP16" />. A K4-free near-triangulation is 3-colourable if and only if it is word-representable ;<ref name="Glen2019">[[arxiv:1605.01688|M. Glen. Colourability and word-representability of near-triangulations, Pure and Applied Mathematics, to appear, 2019.]]</ref>; this result generalises studies in .<ref name="AKM2015">[[arxiv:1405.3527|P. Akrobotu, S. Kitaev, and Z. Masárová. On word-representability of polyomino triangulations. Siberian Adv. Math. 25 (2015), 1−10.]]</ref><ref name="GK2017">[[arxiv:1503.05076|M. 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.]]</ref>. Word-representability of face subdivisions of triangular grid graphs is studied in <ref name="CKS2016">[[arxiv:1503.08002|T. Z. Q. Chen, S. Kitaev, and B. Y. Sun. Word-representability of face subdivisions of triangular grid graphs, Graphs and Combin. 32(5) (2016), 1749−1761.]]</ref> and word-representability of triangulations of grid-covered cylinder graphs is studied in .<ref name="CKS2016-2">[[arxiv:1507.06749|T. Z. Q. Chen, S. Kitaev, and B. Y. Sun. Word-representability of triangulations of grid-covered cylinder graphs, Discr. Appl. Math. 213 (2016), 60−70.]]</ref>.

===Representation of split graphs===

Word-representation of [[Splitsplit graph|split graphs]]s is studied in .<ref name="KLMW2017">[[arxiv:1709.09725|S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725 (2017).]]</ref> <ref name="CKS2019">[[arXiv:1909.09471|T. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split graphs by words, arXiv:1909.09471]]</ref>. In particular, <ref name="KLMW2017" /> offers a characterisation in terms of forbidden induced subgraphs of word-representable split graphs in which vertices in the independent set are of degree at most 2, or the size of the clique is 4, while a computational characterisation of word-representable split graphs with the clique of size 5 is given in .<ref name="CKS2019" />. Also, necessary and sufficient conditions for an orientation of a split graph to be semi-transitive are given in ,<ref name="KLMW2017" />, while in <ref name="CKS2019" /> [[Thresholdthreshold graph|threshold graphs]]s are shown to be word-representable and the split graphs are used to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not result in a word-representable graph, which solved a long-standing open problem.

===Graphs representable by pattern avoiding words===

A graph is '''''p''-representable''' if it can be represented by a word avoiding a [[Permutation pattern|pattern]] ''p''. For example, 132-representable graphs are those that can be represented by words ''w''₁w₂...''w_n'' where there are no 1 ≤ ''a'' < ''b'' < ''c'' ≤ ''n'' such that ''w_a'' < ''w_c'' < ''w_b''. In <ref name="GKZ2017">[[arxiv:1602.08965|A. Gao, S. Kitaev, and P. Zhang. On 132-representable graphs. Australasian J. Combin. 69 (2017), 105−118.]]</ref> it is shown that any 132-representable graph is necessarily a [[circle graph]], and any [[Tree (graph theory)|tree]] and any [[cycle graph]], as well as any graph on at most 5 vertices, are 132-representable. It was shown in <ref name="M2019">[https://www.dmgt.uz.zgora.pl/publish/view_pdf.php?ID=-2009|Y. Mandelshtam. On graphs representable by pattern-avoiding words, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.]</ref> that not all circle graphs are 132-representable, and that 123-representable graphs are also a proper subclass of the class of circle graphs.

==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.

==Open problems==

{{Refimprove section|date=April 2020}}

Open problems on word-representable graphs can be found in,<ref name="KL15" /><ref name=":2" /><ref name=":3" /><ref name=":4" /> and they include:

*Characterise (non-)word-representable planar graphs.

*Characterise word-representable near-triangulations containing the complete graph ''K''₄ (such a characterisation is known for ''K''₄-free planar graphs <ref name="Glen2019">[[arxiv:1605.01688|M. Glen. Colourability and word-representability of near-triangulations, Pure and Applied Mathematics, to appear, 2019.]]</ref>).

*Classify graphs with representation number 3. (See <ref name="Kit2013-3-repr">[[arxiv:1403.1616|S. Kitaev. On graphs with representation number 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.]]</ref> for the state-of-the-art in this direction.)

*Classify graphs with representation number 3.

*Is the [[line graph]] of a non-word-representable graph always non-word-representable?

*Are there any graphs on ''n'' vertices whose representation requires more than floor(''n''/2) copies of each letter?

*Is it true that out of all [[Bipartite graph|bipartite graphsgraph]]s [[Crown graph|crown graphsgraph]]s require longest word-representants? (See <ref name="GKP18" /> for relevant discussion.)

*Characterise word-representable graphs in terms of (induced) forbidden subgraphs.

*Which (hard) problems on graphs can be translated to words representing them and solved on words (efficiently)?

Line 105 ⟶ 104:

== Literature ==

The list of publications to study representation of graphs by words contains, but is not limited to

# [https://cs.uwaterloo.ca/journals/JIS/VOL22/Kitaev/kitaev11.pdf Ö. Akgün, I.P. Gent, S. Kitaev, H. Zantema. Solving computational problems in the theory of word-representable graphs. Journal of Integer Sequences 22 (2019), Article 19.2.5.]

Line 124 ⟶ 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.]

# [https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/wg2.pdf 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.]

# [[arxiv:1501.07108|M. Halldórsson, S. Kitaev and A. Pyatkin. Semi-transitive orientations and word-representable graphs, Discr. Appl. Math. 201 (2016), 164−171.]]

Line 137 ⟶ 136:

# [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.]

# [[arxiv:1709.09725|S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725 (2017).]]

# [[Special:BookSources/978-3-319-25859-1|S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015. {{ISBN |978-3-319-25859-1]]}}.

# [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.]

# [https://link.springer.com/article/10.1134%2FS1990478918020084 S. Kitaev and A. Pyatkin. Word-representable graphs: a Survey, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.]

#[[arxiv:2003.06204|S. Kitaev and A. Pyatkin. On semi-transitive orientability of triangle-free graphs, arXiv:2003.06204v1.]]

#[[arxiv:1903.02777|S. Kitaev and A. Saito. On semi-transitive orientability of Kneser graphs and their complements, Discrete Math., to appear.]]

# [http://120.52.51.19/file.scirp.org/pdf/OJDM20110200008_15101466.pdf S. Kitaev, P. Salimov, C. Severs, and H. Úlfarsson. Word-representability of line graphs, Open Journal of Discrete Mathematics 1 (2011) 2, 96−101.]

# [[arxiv:1102.3980|S. Kitaev, P. Salimov, C. Severs, and H. Úlfarsson (2011) On the representability of line graphs. In: G. Mauri, A. Leporati (eds), Developments in Language Theory. DLT 2011. Lecture Notes Comp. Sci. 6795, Springer, 478−479.]]

# [https://link.springer.com/article/10.1007/s11083-008-9083-7 S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008), 177−194.]

Line 153 ⟶ 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 163 ⟶ 161:

[[Category:Graph families]]

[[Category:NP-complete problems]]