1 Introduction↩︎

The theory of word-representable graphs is an up-and-coming research area. The notion of word-represent-able graphs was first introduced by Sergey Kitaev in the study of the Perkins semigroup [1]. Word-representable graphs generalise several important graph classes, including circle graphs, comparability graphs, and \(3\)-colourable graphs. However, not all graphs are word-representable, and identifying such graphs remains an important problem.

An important problem in the theory of word-representable graphs is to determine word-representations that contain or avoid prescribed patterns. A pattern \(\tau = \tau_1\tau_2\cdots \tau_m\) occurs in a word \(w = w_1w_2\cdots w_n\), if there exists \(1 \leq i_1 < i_2 <\cdots < i_m \leq n\) such that \(\tau_1\tau_2\cdots \tau_m\) is order-isomorphic to \(w_{i_1}w_{i_2}\cdots w_{i_m}\). Based on pattern-avoiding words, Jones et al. [2] introduced the notion of \(u\)-representable graphs, which generalises word-representable graphs. Let \(u \in \mathbb{N}^*\) be a word. The reduction of \(u\), denoted by \(\textit{red}(u)\), is the word obtained by replacing each occurrence of the \(i^{th}\) smallest letter appearing in \(u\) with \(i\). For a word \(u = u_1u_2\cdots u_j \in \mathbb{N}^*\) such that \(\textit{red}(u)=u\), and a word \(w = w_1w_2\cdots w_n \in \mathbb{N}^*\), the word \(w\) has a \(u\)-match starting at position \(i\) if \(\textit{red}(w_i w_{i+1}\cdots w_{i+j-1}) = u\). If \(u \in \{1,2\}^*\) and \(\textit{red}(u)=u\), a labelled graph \(G(V,E)\) with \(V \subseteq \mathbb{N}\) is \(u\)-representable if there exists a word \(w \in V^*\) such that for all \(x,y \in V\), the vertices \(x\) and \(y\) are adjacent if and only if the subword \(w_{x,y}\) contains a \(u\)-match. An unlabelled graph \(H\) is \(u\)-representable if it admits a labelling that results in a \(u\)-representable labelled graph. Word-representable graphs are \(u\)-representable for \(u=11\). However, Kitaev [3] showed that every graph is \(u\)-representable whenever the length of \(u\) is at least three. However, it was shown that not all graphs are \(12\)-representable. Jeff Remmel introduced the notion of a \(k\)-\(11\)-representable graph for a non-negative integer \(k\), providing another generalisation of word-representable graphs. In this representation, an edge of a graph \(G\) corresponds to at most \(k\) occurrences of the consecutive pattern \(11\) in a word representing \(G\). Consequently, word-representable graphs are precisely the \(0\)-\(11\)-representable graphs. It has been shown that every graph is \(2\)-\(11\)-representable via a concatenation of permutations [4], and that \(1\)-\(11\)-representations exist for the Chvátal graph, the Mycielski graph, split graphs, and graphs whose vertex sets can be partitioned into a comparability graph and an independent set [5].

The study of pattern-avoiding word-representations of word-representable graphs was introduced in [6]. Later, Gao et al. [7] studied word-representable graphs that avoid the \(132\)-pattern. They showed that in the \(132\)-avoiding word-representant of a word-representable graph, each letter occurs at most twice; therefore, these graphs are circle graphs. Furthermore, they proved that all trees, cycles, and complete graphs admit \(132\)-avoiding word-representations. On the other hand, Mandelshtam [8] studied the word-representable graphs that avoid the \(123\)-pattern. He showed that each letter appears at most twice in any \(123\)-avoiding word-representant of a word-representable graph, implying that these graphs are also circle graphs. Moreover, all paths, cycles, and complete graphs, but not all trees, are word-representable by \(123\)-avoiding words. In contrast to general word-representable graphs, the existence of both \(132\)-avoiding and \(123\)-avoiding representations depends on vertex labelling. Additionally, A. Takaoka [9] studied \(12\)-representable graphs that avoid patterns of length three. Vertex labelling also plays a crucial role in \(12\)-representations of graphs. In particular, it was shown that graphs avoiding the patterns \(111\), \(121\), \(231\), and \(321\) in their \(12\)-representations correspond to \(12\)-representable graphs, permutation graphs, trivially perfect graphs, and bipartite permutation graphs, respectively. This paper also provides forbidden pattern characterisations for other patterns, including \(123\), \(132\), and \(211\). Forbidden pattern characterisations based on vertex orderings are useful for describing several important graph classes, including interval graphs, permutation graphs, and comparability graphs. For example, a graph \(G\) is an interval graph if and only if there exists a vertex ordering such that, for any three vertices \(x \prec y \prec z\), adjacency of \(x\) and \(z\) implies adjacency of \(y\) and \(z\) [10]. Additional significant results on forbidden-pattern characterisations can be found in [11], [12] and [13].

In addition to permutation patterns, combinatorics on words also studies unordered patterns such as squares, cubes, overlaps, and borders. A word \(u\) is said to contain a word \(v\) as a factor if \(u = xvy\), where \(x\) and \(y\) may be empty. A square (respectively, a cube) in a word consists of two (respectively, three) consecutive equal factors. A word \(w \in \Sigma^*\) contains a square (respectively, a cube) if it can be written as \(w = s_1XXs_2\) (respectively, \(w = s_1XXXs_2\)), where \(s_1,s_2 \in \Sigma^*\) and \(X \in \Sigma^+\). The concept of square-free words gained significant attention in the field of combinatorics on words after the work of Axel Thue in his paper [14]. Thue proved the existence of an infinite number of square-free words over ternary alphabets and opened up the area of combinatorics on words. The notion of a square-free word-representation in the context of word-representable graphs was introduced in the book [6]. In the book, it was shown that word-representable graphs can be represented by cube-free words. Moreover, the existence of trivial square-free word-representations was established for all word-representable graphs except the empty graph on two vertices. In the paper [15], it was shown that there exists a non-trivial square-free word-representation for each word-representable graph except the empty graph of two vertices. Therefore, every word-representable graph, except an empty graph on two vertices, is square-free word-representable. In Observation 25, we prove the existence of a border-free word-representation for word-representable graphs.

As discussed above, pattern-avoidance notions that depend on vertex labelling provide characterisations of certain subclasses of word-representable graphs. However, for unordered patterns that do not depend on specific labellings, most word-representable graphs trivially avoid such patterns. From this, a general question arises about whether there exist label-independent patterns that are unavoidable for certain word-representable graphs but avoidable for others. Another motivation for introducing \(p\)-complete square-free word-representations comes from the definition of adjacency in word-representable graphs. A subword of a word \(w\) is a word obtained by removing certain letters from \(w\). Such subwords need not consist of consecutive letters in the original word, and different letters may appear in arbitrary positions between repeated occurrences. In a word-representation, two vertices are adjacent if and only if they alternate in the subword obtained by restricting the word to those two letters. Thus, adjacency is determined by subwords and not by consecutive factors of the word. In contrast, most unordered patterns studied in combinatorics on words, such as squares, cubes, and overlaps, are defined in terms of factors. Square-free or cube-free word-representations are known to exist for almost all classes of word-representable graphs. On the other hand, pattern-avoiding word-representations such as \(132\)-avoiding and \(123\)-avoiding representations are defined by avoiding these patterns in subwords rather than in factors, and they lead to a more restricted family of word-representable graphs. Motivated by this difference, it is natural to study repetition patterns defined on subwords. The notion of a \(p\)-complete square is based on this idea and leads to new structural properties of word-representable graphs.

In this paper, we define a pattern that provides an affirmative answer to the query mentioned above. This pattern also generalises the concept of square patterns found within a word. As word-representable graphs avoid the simultaneous repetitive occurrences of a factor, we want to extend this square-free property to subwords. We define a \(p\)-complete square by restricting a word to the letters of a given subword. We define the notation of \(p\)-complete square present in the word \(w\) defined over the alphabet \(\Sigma\) by restricting \(w\) to any subset of \(\Sigma\), where the restricted \(w\) contains a square \(XX\), where \(X\in \Sigma^+\) and \(|X|\geq p\). For example, the word \(w=125783462145673818723546\) is defined on the alphabet \(\Sigma=\{1,2,\ldots, 8\}\). If we restricted \(w\) to the \(\{2,5,7,8\}\subset \Sigma\), then the restricted word becomes \(257825788725\). In this case, \(2578\) has two consecutive occurrences; therefore, \(w\) contains a \(4\)-complete square. According to this definition, if \(w\) contains a subword of length at least \(p\) that occurs twice consecutively, then \(w\) contains a \(p\)-complete square. This definition generalises the notion of a square defined on factors, as a factor is an example of a subword. In this paper, we analyse word-representable graphs, focusing on their word-representants that either contain or avoid square-free structures in subwords.

We define the notation of \(p\)-complete square-free word-representable graphs, where a word-representable graph \(G(V,E)\) is represented by a word \(w\) such that when restricting \(w\) to any subset of \(V\), that restricted word does not contain a square \(XX\), where \(X\in V^+\) and \(|X|\geq p\). It is interesting because it allows us to explore whether such specific words can also represent all word-representable graphs. If this is not the case, we can determine which classes of graphs can be represented in this manner. We found that depending on the \(p\) value, some word-representable graphs lose the square-free property when the word representing the graph is restricted to certain subsets of its vertices. Hence, depending on the value of \(p\), the class of \(p\)-complete square-free word-representable graphs forms a proper subclass of word-representable graphs. Since every word-representable graph admits a \(k\)-uniform word-representation, and the minimum word length of many word-representable graphs remains unknown, the precise determination of letter occurrence patterns in non-uniform representations is difficult. Therefore, we restrict our analysis to uniform words when exploring \(p\)-complete square-free word-representations. In this paper, we prove some of the specific properties of the \(p\)-complete square-free uniform words. It is interesting to discover what other graph properties are held in these graphs.

In Section 2, we present the definitions, notations, and basic results used in this paper. In Section 3, we formally define the concept of \(p\)-complete square-free word-representable graphs and \(p\)-complete square-free uniform word-representable graphs. We also show how to create a \(p+1\)-complete square-free uniform word-representable graph from an existing \(p\)-complete square-free uniform word-representable graph. Additionally, we analysed both \(1\)-complete and \(2\)-complete square-free uniform word-representable graphs. We found that each \(K_p\)-free circle graph is a \(p\)-complete square-free uniform word-representable graph. We also show that, for arbitrary \(p\), the recognition problem for \(p\)-complete square-free word-representable graphs is NP-hard. In Section 4, we aim to classify the \(3\)-complete square-free uniform word-representable graphs. We show that only word-representable graphs with a representation number at most \(3\) can be candidates for \(3\)-complete square-free uniform word-representable graphs. Finally, we introduce a method for generating more \(3\)-complete square-free uniform word-representable graphs from a known one.

2 Preliminaries↩︎

In this section, we briefly describe the necessary definitions, notations, and basic results on word-represent-able graphs.

In a word \(w\), if \(x\) and \(y\) alternate, then \(w\) contains \(xyxy\cdots\) or \(yxyx\cdots\) (odd or even length) as a subword.

We denote adjacency between vertices \(x\) and \(y\) by \(x\sim y\), and non-adjacency by \(x\nsim y\). For a word \(w\), \(w_{\{x_1, \cdots, x_m\}}\) denotes the word formed by removing all letters from \(w\) except the letters \(x_1, \ldots, x_m\). In a word \(w\) representing a graph \(G(V,E)\), if \(w_{\{x,y\}}\) is of the form \((xy)^k\), \((yx)^k\), \((xy)^k x\), or \((yx)^k y\), then \(x\) and \(y\) alternate in \(w\), and hence \(x\sim y\) in \(G\). If \(x\nsim y\) in \(G\), then \(x\) and \(y\) do not alternate in \(w\) if at least one of the factors \(xxy\), \(yxx\), \(xyy\), or \(yyx\) occurs in \(w_{\{x,y\}}\).

It can be easily seen that \(\mathcal{R}_1\) contains only complete graphs.

For a \(k\)-uniform word \(w\), \(p_1(w)\) and \(p_k(w)\) are called the initial permutation and final permutation of \(w\), respectively. The initial permutation is denoted by \(\pi(w)\) and the final permutation is denoted by \(\sigma(w)\). In Example 11, \(\pi(w)=142536\) and \(\sigma(w)=152643\). For a word \(w\), \(w_{\{x_1, \cdots, x_m\}}\) denotes the word after removing all letters except the letters \(x_1, \ldots, x_m\) present in \(w\).

In the following, we present the definitions of some patterns and the known results for these patterns.

Since, by definition, every overlap contains a square, removing the square also eliminates the overlap. According to Theorems 23 and 24, there exists a square-free word-representation for a word-representable graph except the empty graph of order \(2\). This implies that every word-representable graph can also be represented by an overlap-free word, as the empty graph with two vertices can be represented by the word \(1122\), where \(1\) and \(2\) represent the vertices of the empty graph. It is clear that the word \(1122\) is overlap-free. Since this word is also border-free, an empty graph with two vertices can also be represented by a border-free word. In the following observation, we prove that for any word-representable graph \(G\), there exists a border-free word \(w\) that represents \(G\). .

Recognition problem of word-representable graph and deciding the representation number of word-representable graphs are \(NP\)-complete problems.

A crown graph \(H_{n,n}\) is obtained from the complete bipartite graph \(K_{n,n}\) by removing a perfect matching. The following theorems show the representation number of a crown graph.

In this paper, the notation \(w=a_1a_2\cdots a_n\) indicates that the word \(w\) contains the factors \(a_1,a_2,\ldots,a_n\), where each \(a_i\) is a possibly empty word. A word \(w\in \Sigma^*\) contains a square if it can be represented by \(w=s_1XXs_2\) where \(X\in \Sigma^+\).

3 \(p\)-complete square-free word-representation↩︎

The formal definition of \(p\)-complete square-free word-representable graphs is described below. All graphs considered in this paper are undirected graphs.

Now, using this concept of \(p\)-complete square-free word, we define \(p\)-complete square-free word-representable graphs.

If a word \(w\) representing a graph \(G(V,E)\) contains a \(p\)-complete square \(XX\), where \(X\in V^{+}\) and \(p=\left\lceil \frac{|w|}{2} \right\rceil\), then \(w\) must be of the form \(XX\). By Theorems 23 and 24, this square can be removed, and the resulting word still represents the graph \(G\). Therefore, we do not define \(p\)-complete square-free word-representable graphs for the case \(p=\left\lceil \frac{|w|}{2} \right\rceil\).

The graph shown in Figure [fig1] can be represented with the \(2\)-uniform word \(23123414\) and the non-uniform word \(23414\). We can observe that the \(2\)-uniform word is \(4\)-complete square-free (where \(w_{\{1,2,3\}}=231231\) is a square), while the non-uniform word is a \(3\)-complete square-free word. Additionally, \(2312341\) is another non-uniform word that represents this graph; however, this word is 4-complete square-free (where \(w_{\{1,2,3\}} = 231231\) is a square).

According to Theorem 5, every word-representable graph has a \(k\)-uniform word-representant. Based on this uniform word-representation, we can explore the possible \(p\)-complete square-free word-representations of word-representable graphs, since we know the exact number of times each letter can occur in that uniform word. However, the minimum word length for many word-representable graphs remains unknown, preventing us from determining the exact occurrence of letters in non-uniform words. Therefore, our focus is primarily on uniform words. We specifically define the notion of a \(p\)-complete square-free uniform word in the context of uniform words. Subsequently, we characterise \(k\)-uniform word-representable graphs for \(k\leq 3\), in relation to \(p\)-complete square-free words.

Since the class of word-representable graphs is hereditary, we investigate whether the class of \(p\)-complete square-free word-representable graphs is hereditary as well. We provide an affirmative answer in the following lemma.

According to the definition of \(p\)-complete square-free uniform words, if a word-representable graph \(G\) has a complete square-free uniform representation number \(p\), then \(G\) is also \((p+1)\)-complete square-free uniform word-representable.

According to Theorems 23 and 24, every word-representable graph has a square-free representation except an empty graph of two vertices. This provides an upper bound on the size of a subset \(S\subseteq V\) for a word-representable graph \(G(V,E)\), such that \(w_{S}\) contains a \(p-1\)-complete square, where \(w\) is a \(p\)-complete square-free uniform representation of the graph \(G\).

Suppose \(G(V,E)\) is a word-representable graph with a representation number of \(k\). Let \(\mathcal{W}\) be the set containing all \(k\)-uniform words that represent the graph \(G\). It is not necessarily true that if there exists a word \(w \in \mathcal{W}\) that is \(p\)-complete square-free, then all words \(w' \in \mathcal{W}\) will also be \(p\)-complete square-free. In the paper [20], it was shown that the representation number of the crown graph \(H_{n,n}\) is \(\lceil n/2 \rceil\) for \(n \geq 5\). The authors also provided a word representation for the \(H_{n,n}\) graph. According to that representation, the word \(w = 1234'43'2'1'1243'34'2'1'1342'24'3'1'2341'14'3'2'\) represents the \(H_{4,4}\) graph, where the vertices are partitioned into two independent sets \(X = \{1,2,3,4\}\) and \(Y = \{1',2',3',4'\}\). It can be easily verified that \(w\) is a \(5\)-complete square-free word. Now, if we exchange the positions of the last occurrences of \(3'\) and \(4'\) in the word \(w\), we can form a new word \(w' = 1234'43'2'1'1243'34'2'1'1342'24'3'1'2341'13'4'2'\). It is clear that \(w'\) still represents the \(H_{4,4}\) graph. However, this new word \(w'\) is a \(7\)-complete square-free word. This is because the \(w_{\{1,4',3'\}} = 14'3'13'4'14'3'13'4'\) contains a square \(XX\), where \(X=14'3'13'4'\) and \(|X|= 6\).

From this example, we can also conclude that for any word \(w \in \mathcal{W}\), if we consider a subset \(S \subseteq V\) and the word \(w_{S}\) contains a square \(XX\) where \(X\in S^+\) and \(|X| = p - 1\), the size of \(S\) may not necessarily be \(p - 1\).

We attempt to determine whether removing a vertex from a \(p\)-complete square-free uniform word-representable graph transforms it into a \((p-1)\)-complete square-free uniform word-representable graph.

We now study the role of apex vertices in \(p\)-complete square-free uniform representations. We discovered that in a \(p\)-complete square-free uniform word-representable graph \(G(V,E)\), if there exists an apex vertex \(v\), then \(v\) must be in every subset \(S\) of \(V\) where \(w_{S}\) contains a square \(XX\), where \(X\in S^+\) and \(|X|=p-1\). We prove this lemma below.

In a \(p\)-complete square-free uniform word-representable graph \(G(V,E)\), the apex vertex is present in every subset \(S\) of the vertices that contains a square \(XX\), where \(X\in S^+\) and \(|X|=p-1\). Thus, removing the apex vertex creates a \((p-1)\)-complete square-free uniform word-representable graph. We can prove this statement using the theorem below.

According to Lemma 3, in a \(p\)-complete square-free uniform word-representable graph \(G(V,E)\), an apex vertex can appear in any subset \(S\subseteq V\) where \(w_{S}\) contains a square \(XX\), \(X\in S^+\) and \(|X|=p-1\). Here, \(w\) represents the \(p\)-complete square-free uniform word of \(G\). It is straightforward to prove that all \(p\)-complete square-free uniform words for the graph \(G(V,E)\) contain the apex vertex in every subset of \(V\), where the word is restricted to that subset containing a square \(XX\), where \(X\in V^+\) and \(|X|=p-1\). Based on this, we introduce the notation of a \(p\)-complete square vertex and \(p\)-complete square vertex set as follows.

Given a \(p\)-complete square vertex, we present a method for constructing a \((p+1)\)-complete square-free uniform word-representable graph from a known \(p\)-complete square-free uniform word-representable graph. We replace a \(p\)-complete square vertex with a \(K_2\) module as described in the following theorem.

Next, we derive a forbidden induced subgraph characterisation. We want to find the word-representable graphs, which are \(p\)-complete square-free uniform word-representable. We found out that \(p\)-complete square-free uniform word-representable graphs avoid \(K_p\) as an induced subgraph. We prove this statement in the following theorem.

However, the converse of this theorem is not true. Later, in Theorem 51, we provide an example that contradicts the converse statement of Theorem 43.

According to Theorem 47, a word-representable graph can be \(p\)-complete square-free uniform word-representable based on \(p\)-value. At first, we focus on identifying the \(p\)-complete square-free uniform word-representable graphs when \(p=1\). In the following lemma, we prove that only complete graphs have such a word-representation.

From Lemma 4, we know that only the complete graph is \(1\)-complete square-free representable. Therefore, the complete graph is a \(p\)-complete square-free uniform word-representable graph for \(p>1\). Hence, in the following discussions, all the graphs we considered are not complete graphs.

A \(2\)-complete square-free uniform word-representable graph does not contain \(K_2\) as a subgraph. The only \(K_2\)-free graph is an empty graph, which is \(2\)-complete square-free uniform word-representable. We prove this statement below.

From Theorem 43, we obtain the following result.

Since an empty graph is only \(2\)-complete square-free uniform word-representable, we will check whether the other \(2\)-representable graphs are \(p\)-complete square-free uniform. For a \(K_p\)-free circle graph, there exists a \(p\)-complete square-free uniform word-representation. Using Theorem 7, we prove the following theorem.

Suppose \(w\) is a \(p\)-complete square-free uniform word-representation of a graph \(G\). By the definition of a \(p\)-complete square-free uniform word-representable graph, the value of \(p\) is at most \(\left\lceil \frac{|w|}{2} \right\rceil\). In the following theorem, we show that for a word-representable graph \(G(V,E)\) with representation number \(k \ge 3\), the value of \(p\) is at most \(\left\lceil \frac{kn}{2} \right\rceil - 1\), where \(|V| = n\). This provides a tighter upper bound on possible values of \(p\).

From Theorem 47, we obtain the following corollary.

Theorem 47 provides an upper bound on the value of \(p\) in terms of the representation number of a graph. However, this bound need not be tight, and the obtained value of \(p\) may be larger than the complete square-free uniform representation number. In the next section, we study the relationship between the representation number and the complete square-free uniform representation number. In particular, we establish this connection for complete square-free uniform representation numbers up to \(3\).

4 \(3\)-complete square-free uniform word↩︎

According to Theorem 46, all triangle-free (\(K_3-free\)) circle graphs are \(3\)-complete square-free uniform word-representable. Every \(2\)-uniform square-free word representing a \(K_3\)-free graph \(G\) is also a \(3\)-complete square-free uniform word. We now examine whether every \(K_3\)-free word-representable graph with representation number \(k \ge 3\) admits a \(3\)-complete square-free uniform word-representation. In the following theorem, we prove that a \(3\)-complete square-free uniform word-representation does not exist for a graph with representation number \(k>3\).

From Theorem 51, we can obtain an example that contradicts the converse statement of Theorem 43. We know that the crown graph is bipartite, so it avoids \(K_3\) as an induced subgraph. According to Theorems 28 and 29, the representation number of the crown graph \(H_{n,n}\) is \(\lceil n/2 \rceil\), \(n\geq 5\). Thus, the representation number of the \(H_{8,8}\) graph is \(\lceil 8/2 \rceil=4\). However, according to Theorem 51, the \(H_{8,8}\) graph cannot contain \(p\)-complete square-free uniform word-representation, when \(p=3\). Therefore, there exist word-presentable graphs that are \(K_p\)-free but are not \(p\)-complete square-free uniform word-representable.

According to Theorem 51, it can be directly seen that the graphs with a representation number \(\leq 3\) can have the complete square-free uniform representation number \(3\). Now, we aim to determine whether it is possible to construct a \(3\)-complete square-free uniform word-representable graph from an existing \(3\)-complete square-free uniform word-representable graph.

If we add an apex vertex to an empty graph, the graph becomes a star graph. Since the star graph is \(K_3\)-free and \(2\)-uniform word-representable, according to Theorem 46, the star graph is \(3\)-complete square-free uniform word-representable. However, if we connect an apex vertex with a non-empty \(3\)-complete square-free uniform word-representable graph, the resulting graph is no longer \(3\)-complete square-free uniform word-representable. We prove this statement below.

To create a \(3\)-complete square-free uniform word, connecting an apex vertex to a \(3\)-complete square-free uniform word-representable graph does not work. Therefore, we need another operation to create a new \(3\)-complete square-free uniform word-representable graph. We create a method using the occurrence-based function, and we obtain a word-representation of a new \(3\)-complete square-free uniform word-representable graph from a known \(3\)-complete square-free uniform word-representable graph. The definition of an occurrence-based function is described below.

Suppose \(w\) is a \(3\)-complete square-free uniform word that represents the graph \(G(V,E)\). By applying an occurrence-based function to \(w\), we can obtain a \(3\)-complete square-free uniform word that represents the graph \(G'(V\cup \{v\}, E\cup \{v\sim u: u\in N_x\})\) where \(N_x\) is the set that contains the neighbours of \(x\) in the graph \(G\).

It is well known that cycle graphs are \(2\)-word-representable. In this example, we apply the construction described in Theorem 55 to obtain a \(3\)-uniform square-free word representation of an extended graph.

We prove that word-representable graphs \(G\) with representation numbers \(> 3\) do not have 3-complete square-free uniform words. It remains open whether all \(K_3\)-free graphs with representation number \(3\) are \(3\)-complete square-free uniform word-representable.

5 Conclusion↩︎

We introduced the notion of a \(p\)-complete square-free uniform word-representation and derived several of its fundamental properties. We described a constructive process for obtaining a \((p+1)\)-complete square-free uniform word-representable graph from a \(p\)-complete square-free uniform word-representable graph. We also showed that graphs with representation number at most \(3\) can have a \(3\)-complete square-free uniform word-representation. We conclude by listing several open problems and possible directions for further research related to these topics.

1. Characterise the word-representable graphs with representation number at least \(3\) that admit \(p\)-complete square-free uniform word-representations for \(p>3\).

2. Determine the word-representable graphs with representation number at least \(3\) that do not admit any \(p\)-complete square-free uniform word-representation for \(p>3\).

3. Characterise \(p\)-complete square-free uniform word-representable graphs.

4. Since every \(K_3\)-free \(2\)-representable graph is \(3\)-complete square-free uniformly word-representable, it is natural to study the enumeration of \(3\)-complete square-free uniform word-representations of \(2\)-representable \(K_3\)-free graphs.

5. We showed that \(3\)-complete square-free uniform word-representable graphs cannot have representation number greater than \(3\). It remains open whether a similar result holds for \(p\)-complete square-free uniform word-representable graphs with \(p>3\). In particular, does there exist a word-representable graph \(G\) whose representation number is greater than \(p\), while its complete square-free uniform representation number is at most \(p\)?

References↩︎