(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.
[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.
[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.
These fields are algebra, graph theory, computer science, combinatorics on words, and scheduling.
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.
[6][7] 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.
In 2014, Vincent Limouzy observed that it is an NP-complete problem to recognise whether a given graph is word-representable.
[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.
[3] Non-isomorphic non-word-representable connected graphs on at most eight vertices were first enumerated by Heman Z.Q.
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.
[14] Edge-deletion, edge-addition and edge-lifting with respect to word-representability (equivalently, semi-transitive orientability) are 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.
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.
[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.