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 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's word-representant, and one says that that w represents G. 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 in 2004 based on joint research with Steven SeifS. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008), 177−194. on the Perkins semigroup, which has played an important role in semigroup theory since 1960.S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015. The first systematic study of word-representable graphs was undertaken in a 2008 paper by Kitaev and Artem Pyatkin,S. Kitaev and A. Pyatkin. On representable graphs, J. Autom., Lang. and Combin. 13 (2008), 45−54. starting development of the theory. One of key contributors to the area is Magnús M. Halldórsson.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.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.M. Halldórsson, S. Kitaev and A. Pyatkin. Semi-transitive orientations and word-representable graphs, Discr. Appl. Math. 201 (2016), 164−171. Up to date, 35+ papers have been written on the subject, and the core of the book 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.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.S. Kitaev and A. Pyatkin. Word-representable graphs: a Survey, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25,номер 2, 19−53

Motivation to study the graphs

According to, 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 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 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 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.

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. A graph is word-representable implies that the neighbourhood of each vertex is permutationally representable (i.e. is a comparability graph). Converse to the last statement is not true. 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.

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

For n ≥ 2, the wheel graph W2n+1, which consists of a cycle of length 2n + 1 and an additional vertex connected to all vertices in the cycle, is not word-representable. In particular, W5 is the smallest (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. 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 A. Collins, S. Kitaev, and V. Lozin. New results on word-representable graphs, Discr. Appl. Math. 216 (2017), 136–141. and non-word-representable triangle-free graphs exist. Regular non-word representable graphs also exist. 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,Ö. 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. 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. The operations not necessarily preserving word-representability are taking the complement, taking the line graph, edge contraction, gluing two graphs in a clique of size 2 or more, tensor product, lexicographic product and strong product.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. Edge-deletion, edge-addition and edge-lifting with respect to word-representability (equivalently, semi-transitive orientability) are studied in.

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, the highest known representation number is floor(n/2) given by crown graphs with an all-adjacent vertex. Interestingly, such graphs are not the only graphs that require long representations.Ö. 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. Crown graphs themselves are shown to require long (possibly longest) representations among bipartite graphs.M. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph, Discr. Appl. Math. 244, 2018, 89–93.

Computational complexity

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

PROBLEMCOMPLEXITYdeciding word-representabilityNP-completeDominating SetNP-hardClique CoveringNP-hardMaximum Independent SetNP-hardMaximum Cliquein Papproximating the graph representation number within a factor n1−ε for any ε > 0NP-hard

Representation of planar graphs

Triangle-free planar graphs are word-representable. A K4-free near-triangulation is 3-colourable if and only if it is word-representable;M. Glen. Colourability and word-representability of near-triangulations, Pure and Applied Mathematics, to appear, 2019. this result generalises studies in.P. Akrobotu, S. Kitaev, and Z. Masárová. On word-representability of polyomino triangulations. Siberian Adv. Math. 25 (2015), 1−10.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. Word-representability of face subdivisions of triangular grid graphs is studied in 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. and word-representability of triangulations of grid-covered cylinder graphs is studied in.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.

Representation of split graphs