Word-representable graph
In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word 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. 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
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 Seif on the Perkins semigroup, which has played an important role in semigroup theory since 1960. The first systematic study of word-representable graphs was undertaken in a 2008 paper by Kitaev and Artem Pyatkin, starting development of the theory. One of key contributors to the area is . 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.Motivation to study the graphs
According to, word-representable graphs are relevant to various fields, thus providing a motivation 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 iff 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 -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, , 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 . Moreover, 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 . 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 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-representable, where κ is the size of a maximal clique in G. As an immediate corollary of the last statement, one has that the of word-representability is in NP. In 2014, 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
W2n+1, for n ≥ 2, are not word-representable and W5 is the minimum non-word-representable graph. Taking any non-comparability graph and adding an apex, 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, and a vertex of degree at least 5. Non-word-representable graphs of maximum degree 4 exist 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, 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 .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. Edge-deletion, edge-addition and edge-lifting with respect to word-representability are studied in.Graphs with high representation number
While each non-complete word-representable graph G is 2-representable, where κ is the size of a maximal clique in G, the highest known representation number is floor given by crown graphs with an all-adjacent vertex. Interestingly, such graphs are not the only graphs that require long representations. Crown graphs themselves are shown to require long representations among bipartite graphs.Computational complexity
Known computational complexities for problems on word-representable graphs can be summarised as follows :| PROBLEM | COMPLEXITY |
| deciding word-representability | NP-complete |
| Dominating Set | NP-hard |
| Clique Covering | NP-hard |
| Maximum Independent Set | NP-hard |
| in P | |
| approximating the graph representation number within a factor n1−ε for any ε > 0 | NP-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 ; this result generalises studies in. Word-representability of face subdivisions of triangular grid graphs is studied in and word-representability of triangulations of grid-covered cylinder graphs is studied in.Representation of split graphs
Word-representation of split graphs is studied in. In particular, 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. Also, necessary and sufficient conditions for an orientation of a split graph to be semi-transitive are given in, while in 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 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 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 of the notion of a word-representable graph are based on the observation by that non-edges are defined by occurrences of the pattern 11 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.Another way to generalise the notion of a word-representable graph, again suggested by , 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. Note that 0-11-representable graphs are precisely word-representable graphs. The key results in 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. 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 , and they include:- Characterise word-representable planar graphs.
- Characterise word-representable near-triangulations containing the complete graph K4.
- 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 copies of each letter?
- Is it true that out of all bipartite graphs crown graphs require longest word-representants?
- Characterise word-representable graphs in terms of forbidden subgraphs.
- Which problems on graphs can be translated to words representing them and solved on words ?
Literature
- B. Broere. Word representable graphs, 2018. Master thesis at Radboud University, Nijmegen.
- M. Glen. On word-representability of polyomino triangulations & crown graphs, 2019. PhD thesis, University of Strathclyde.
- S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015..
#
-
Software
#