Word-representable graph

Last updated

In the mathematical field of graph theory, a word-representable graph is a 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 balternate 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.

Contents

The word w is G's word-representant, and one says that that wrepresentsG. The smallest (by the number of  vertices) non-word-representable graph is the wheel graph W5, 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. Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. Various generalisations of the theory of word-representable graphs accommodate representation of any graph.

History

Word-representable graphs were introduced by Sergey Kitaev [1] in 2004 based on joint research with Steven Seif [2] on the Perkins semigroup , which has played an important role in semigroup theory since 1960. [3] The first systematic study of word-representable graphs was undertaken in a 2008 paper by Kitaev and Artem Pyatkin, [4] starting development of the theory. One of key contributors to the area is Magnús M. Halldórsson. [5] [6] [7] Up to date, 35+ papers have been written on the subject, and the core of the book [3] 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. [8] [9] [10]

Motivation to study the graphs

According to, [3] word-representable graphs are relevant to various fields, thus motivating 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. circle graphs, 3-colorable graphs and comparability graphs.

Early results

It was shown in [4] that a graph G is word-representable if 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 + 1)-representable. Thus, the notion of the representation number of a graph, as the minimumk 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 complete graphs, while graphs with representation number 2 are precisely the class of circle non-complete graphs. In particular, forests (except for single trees on at most 2 vertices), ladder graphs and cycle graphs have representation number 2. No classification for graphs with representation number 3 is known. However, there are examples of such graphs, e.g. Petersen's graph and prisms. Moreover, the 3-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 minor. [4]

A graph G is permutationally representable if it can be represented by a word of the form p1p2...pk, where pi is a permutation. On can also say that G is permutationally k-representable. A graph is permutationally representable iff it is a comparability graph. [2] A graph is word-representable implies that the neighbourhood of each vertex is permutationally representable (i.e. is a comparability graph). [2] Converse to the last statement is not true. [5] However, the fact that the neighbourhood of each vertex is a comparability graph implies that the Maximum Clique problem is polynomially solvable on word-representable graphs. [6] [7]

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 acyclic and for any directed path u1→u2→ ...→ut, t ≥ 2, either there is no edge from u1 to ut or all edges ui → uj 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. [7] 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 − κ(G))-representable, where κ(G) is the size of a maximal clique in G. [7] As an immediate corollary of the last statement, one has that the recognition problem of word-representability is in NP. In 2014, Vincent Limouzy observed that it is an NP-complete problem to recognise whether a given graph is word-representable. [3] [8] Another important corollary to the key theorem is that any 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

Non-word-representable graphs

Wheel graphs W2n+1, for n ≥ 2, are not word-representable and W5 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. [3] 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 [11] and non-word-representable triangle-free graphs exist. [6] Regular non-word representable graphs also exist. [3] 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, [12] 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 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. [3] The operations not necessarily preserving word-representability are taking the complement, taking the line graph, edge contraction, [3] gluing two graphs in a clique of size 2 or more, [13] tensor product, lexicographic product and strong product. [14] Edge-deletion, edge-addition and edge-lifting with respect to word-representability (equivalently, semi-transitive orientability) are studied in. [14]

Graphs with high representation number

While each non-complete word-representable graph G is 2(n − κ(G))-representable, where κ(G) is the size of a maximal clique in G, [7] the highest known representation number is floor(n/2) given by crown graphs with an all-adjacent vertex. [7] Interestingly, such graphs are not the only graphs that require long representations. [15] Crown graphs themselves are shown to require long (possibly longest) representations among bipartite graphs. [16]

Computational complexity

Known computational complexities for problems on word-representable graphs can be summarised as follows: [3] [8]

PROBLEMCOMPLEXITY
deciding word-representabilityNP-complete
Dominating Set NP-hard
Clique Covering NP-hard
Maximum Independent Set NP-hard
Maximum Clique in P
approximating the graph representation number within a factor n1−ε for any ε > 0NP-hard

Representation of planar graphs

Triangle-free planar graphs are word-representable. [7] A K4-free near-triangulation is 3-colourable if and only if it is word-representable; [17] this result generalises studies in. [18] [19] Word-representability of face subdivisions of triangular grid graphs is studied in [20] and word-representability of triangulations of grid-covered cylinder graphs is studied in. [21]

Representation of split graphs

Word-representation of split graphs is studied in. [22] [13] In particular, [22] 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. [13] Also, necessary and sufficient conditions for an orientation of a split graph to be semi-transitive are given in, [22] while in [13] threshold graphs 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 pattern p. For example, 132-representable graphs are those that can be represented by words w1w2...wn where there are no 1 ≤ a < b < c ≤ n such that wa < wc < wb. In [23] it is shown that any 132-representable graph is necessarily a circle graph, and any tree and any cycle graph, as well as any graph on at most 5 vertices, are 132-representable. It was shown in [24] 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 [25] [26] [27] of the notion of a word-representable graph are based on the observation by 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. [28]

Another way to generalise the notion of a word-representable graph, again suggested by 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. [29] Note that 0-11-representable graphs are precisely word-representable graphs. The key results in [29] 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. [15] 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

Open problems on word-representable graphs can be found in, [3] [8] [9] [10] and they include:

Literature

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

  1. Ö. 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.
  2. P. Akrobotu, S. Kitaev, and Z. Masárová. On word-representability of polyomino triangulations. Siberian Adv. Math. 25 (2015), 1−10.
  3. B. Broere. Word representable graphs, 2018. Master thesis at Radboud University, Nijmegen.
  4. B. Broere and H. Zantema. "The k-cube is k-representable," J. Autom., Lang., and Combin. 24 (2019) 1, 3-12.
  5. J. N. Chen and S. Kitaev. On the 12-representability of induced subgraphs of a grid graph, Discussiones Mathematicae Graph Theory, to appear
  6. T. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split graphs by words, arXiv:1909.09471
  7. 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.
  8. 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.
  9. G.-S. Cheon, J. Kim, M. Kim, and S. Kitaev. Word-representability of Toeplitz graphs, Discr. Appl. Math., to appear.
  10. G.-S. Cheon, J. Kim, M. Kim, and A. Pyatkin. On k-11-representable graphs. J. Combin. 10 (2019) 3, 491−513.
  11. 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.
  12. A. Collins, S. Kitaev, and V. Lozin. New results on word-representable graphs, Discr. Appl. Math. 216 (2017), 136−141.
  13. A. Daigavane, M. Singh, B.K. George. 2-uniform words: cycle graphs, and an algorithm to verify specific word-representations of graphs. arXiv:1806.04673 (2018).
  14. 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.
  15. M. Gaetz and C. Ji. Enumeration and Extensions of Word-representants, arXiv:1909.00019.
  16. 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.
  17. A. Gao, S. Kitaev, and P. Zhang. On 132-representable graphs. Australasian J. Combin. 69 (2017), 105−118.
  18. M. E. Glen. Colourability and word-representability of near-triangulations, Pure Mathematics and Applications, 28(1), 2019, 70−76.
  19. M. E. Glen. On word-representability of polyomino triangulations & crown graphs, 2019. PhD thesis, University of Strathclyde.
  20. 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.
  21. M. E. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph, Discr. Appl. Math. 244, 2018, 89−93.
  22. M.M. Halldórsson, S. Kitaev, A. Pyatkin On representable graphs, semi-transitive orientations, and the representation numbers, arXiv:0810.0310 (2008).
  23. 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.
  24. 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.
  25. M. Halldórsson, S. Kitaev and A. Pyatkin. Semi-transitive orientations and word-representable graphs, Discr. Appl. Math. 201 (2016), 164−171.
  26. 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).
  27. S. Kitaev. On graphs with representation number 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.
  28. 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.
  29. S. Kitaev. Existence of u-representation of graphs, Journal of Graph Theory 85 (2017) 3, 661−668.
  30. S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725 (2017).
  31. S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015. ISBN   978-3-319-25859-1.
  32. S. Kitaev and A. Pyatkin. On representable graphs, J. Autom., Lang. and Combin. 13 (2008), 45−54.
  33. S. Kitaev and A. Pyatkin. Word-representable graphs: a Survey, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.
  34. S. Kitaev and A. Pyatkin. On semi-transitive orientability of triangle-free graphs, arXiv:2003.06204v1.
  35. S. Kitaev and A. Saito. On semi-transitive orientability of Kneser graphs and their complements, Discrete Math., to appear.
  36. 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.
  37. S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008), 177−194.
  38. E. Leloup. Graphes représentables par mot. Master Thesis, University of Liège, 2019
  39. Mandelshtam. On graphs representable by pattern-avoiding words, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  40. С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25,номер 2, 19−53.

Software

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

  1. 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.
  2. H. Zantema. Software REPRNR to compute the representation number of a graph, 2018. Available at https://www.win.tue.nl/~hzantema/reprnr.html.

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

In the mathematical field of graph theory, a vertex-transitive graph is a graph G in which, given any two vertices v1 and v2 of G, there is some automorphism

In geometry, a polytope or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in the same or reverse order, and with the same angles between corresponding faces.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.

<span class="mw-page-title-main">Heawood graph</span> Undirected graph with 14 vertices

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

<span class="mw-page-title-main">Symmetric graph</span> Graph in which all ordered pairs of linked nodes are automorphic

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism

<span class="mw-page-title-main">Coxeter graph</span> Cubic graph with 28 vertices and 42 edges

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

<span class="mw-page-title-main">Foster graph</span> Bipartite 3-regular graph with 90 vertices and 135 edges

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

<span class="mw-page-title-main">Shrikhande graph</span> Undirected graph named after S. S. Shrikhande

In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether or not the pair of nodes is connected.

<span class="mw-page-title-main">Biggs–Smith graph</span> Cubic distance-regular graph with 102 nodes and 153 edges

In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.

<span class="mw-page-title-main">Dyck graph</span>

In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.

<span class="mw-page-title-main">Nauru graph</span> 24-vertex symmetric bipartite cubic graph

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

<span class="mw-page-title-main">F26A graph</span>

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

<span class="mw-page-title-main">Ljubljana graph</span> Undirected bipartite graph with 112 vertices and 168 edges

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges, rediscovered in 2002 and named after Ljubljana.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, γ∞(G), is the minimum number of vertices possible in the initial set D. For example, the eternal domination number of the cycle on five vertices is two.

References


  1. ↑ Steingrímsson, Einar (2023). "The history of the Gothenburg–Reykjavík–Strathclyde Combinatorics Group" (PDF). Enumerative Combinatorics and Applications. 3 (1): Article S1H1. doi:10.54550/ECA2023V3S1H1.
  2. 1 2 3 S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008), 177−194.
  3. 1 2 3 4 5 6 7 8 9 10 S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015. ISBN   978-3-319-25859-1
  4. 1 2 3 S. Kitaev and A. Pyatkin. On representable graphs, J. Autom., Lang. and Combin. 13 (2008), 45−54.
  5. 1 2 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.
  6. 1 2 3 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.
  7. 1 2 3 4 5 6 7 M. Halldórsson, S. Kitaev and A. Pyatkin. Semi-transitive orientations and word-representable graphs, Discr. Appl. Math. 201 (2016), 164−171.
  8. 1 2 3 4 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.
  9. 1 2 S. Kitaev and A. Pyatkin. Word-representable graphs: a Survey, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.
  10. 1 2 С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25,номер 2, 19−53
  11. ↑ A. Collins, S. Kitaev, and V. Lozin. New results on word-representable graphs, Discr. Appl. Math. 216 (2017), 136–141.
  12. ↑ Ö. 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.
  13. 1 2 3 4 T. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split graphs by words, arXiv:1909.09471
  14. 1 2 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.
  15. 1 2 Ö. 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.
  16. 1 2 M. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph, Discr. Appl. Math. 244, 2018, 89–93.
  17. 1 2 M. Glen. Colourability and word-representability of near-triangulations, Pure and Applied Mathematics, to appear, 2019.
  18. ↑ P. Akrobotu, S. Kitaev, and Z. Masárová. On word-representability of polyomino triangulations. Siberian Adv. Math. 25 (2015), 1−10.
  19. ↑ 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.
  20. ↑ 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.
  21. ↑ 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.
  22. 1 2 3 S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725 (2017).
  23. ↑ A. Gao, S. Kitaev, and P. Zhang. On 132-representable graphs. Australasian J. Combin. 69 (2017), 105−118.
  24. ↑ Mandelshtam. On graphs representable by pattern-avoiding words, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  25. ↑ 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).
  26. ↑ 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.
  27. ↑ M. Gaetz and C. Ji. Enumeration and Extensions of Word-representants, arXiv:1909.00019.
  28. ↑ S. Kitaev. Existence of u-representation of graphs, Journal of Graph Theory 85 (2017) 3, 661−668.
  29. 1 2 G.-S. Cheon, J. Kim, M. Kim, and A. Pyatkin. On k-11-representable graphs. J. Combin. 10 (2019) 3, 491−513.
  30. ↑ S. Kitaev. On graphs with representation number 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.