On 1-11-representability and multi-1-11-representability of graphs

Alshammari, Mohammed; Kitaev, Sergey; Tang,  Chaoliang; Tao, Tianyi; Zhang, Junchi

doi:10.61091/um122-02

Abstract

1. Introduction
2. Preliminaries
3. Graphs on at most 8 vertices
4. Multi-1-11-representation number of a graph
5. Concluding remarks

References

Utilitas Mathematica

Volume 122
Pages: 29-40

Research article

On 1-11-representability and multi-1-11-representability of graphs

^¹, ^¹, ^², ^², ^²

¹Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, United Kingdom

²Shanghai Center for Mathematical Sciences, Fudan University, 220 Handan Road, Shanghai 200433, China

Received: 29/01/2025
Accepted: 07/03/2025
Published Online: 22/03/2025

Copyright Link
License

Abstract

Jeff Remmel introduced the concept of a $k$ -11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of word-representable graphs, which are exactly 0-11-representable graphs. A graph $G$ is $k$ -11-representable if it can be represented by a word $w$ such that for any edge (resp., non-edge) $x y$ in $G$ the subsequence of $w$ formed by $x$ and $y$ contains at most $k$ (resp., at least $k + 1$ ) pairs of consecutive equal letters. A remarkable result of Cheon et al. is that any graph is 2-11-representable, while it is still unknown whether every graph is 1-11-representable. Cheon et al. showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs, which was extended by additional powerful tools suggested by Futorny et al. in 2024. In this paper, we prove that all graphs on at most 8 vertices are 1-11-representable hence extending the known fact that all graphs on at most 7 vertices are 1-11-representable. Also, we discuss applications of our main result in the study of multi-1-11-representation of graphs we introduce in this paper analogously to the notion of multi-word-representation of graphs suggested by Kenkireth and Malhotra in 2023.

Keywords: 1-11-representable graph, multi-1-11- representation of graphs, word-representable graph

1. Introduction

Various methods for representing graphs extend far beyond the conventional use of adjacency or incidence matrices; for example, see [9] for a discussion. Of particular relevance to our paper are representations of graphs by words or sequences, where adjacency between a pair of vertices is determined by the occurrence of a fixed pattern in the subword or subsequence formed by the vertices. For instance, in the extensively studied word-representable graphs [6], first studied in [7] and defined in Subsection 2.1, edges are determined by the strict alternation of vertices.

Another representation method is $k$ -11-representation, introduced by Jeff Remmel in 2017 and defined in Subsection 2.2, where at most $k$ violations of strict alternation are allowed to define an edge between two vertices. Consequently, word-representable graphs correspond precisely to 0-11-representable graphs. The concept of $k$ -11-representable graphs was first studied by Cheon et al. [2].

While not all graphs are word-representable, all graphs are known to be 2-11-representable [2]. The most intriguing open question in the theory of $k$ -11-representable graphs is whether all graphs are 1-11-representable, and it remains challenging to predict an answer to this question. Recent research in this area has focused on developing powerful tools to study 1-11-representable graphs [3]; see Subsection 2.2.

1.1. Our main results and the organization of the paper

In Section 2, we introduce the necessary definitions and known results that will be used throughout this paper. In Section 3, we prove that all graphs with at most 8 vertices are 1-11-representable, thereby extending the previously known result that all graphs with at most 7 vertices are 1-11-representable [2,3]. In Section 4, we introduce the concept of the multi- $k$ -11-representation number of a graph, which generalizes the notion of the multi-word-representation number of a graph [5].

As an application of our main results in this paper, in Section 4, we demonstrate that all graphs with at most 24 vertices have a multi-1-11-representation number of at most 2. Finally, in Section 5, we provide concluding remarks and outline open problems.

2. Preliminaries

An orientation of a graph is transitive, if the presence of the edges $u \to v$ and $v \to z$ implies the presence of the edge $u \to z$ . An undirected graph $G$ is a comparability graph if $G$ admits a transitive orientation.

2.1. Word-representable graphs and semi-transitive orientations

Two letters $x$ and $y$ alternate in a word $w$ if, after deleting all letters in $w$ except for $x$ and $y$ , we obtain either the word $x y x y \dots$ or $y x y x \dots$ (of even or odd length). A graph $G = (V, E)$ is word-representable if and only if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ , with $x \neq y$ , alternate in $w$ if and only if $x y \in E$ . The word $w$ is called a word-representant for $G$ .

The unique minimum (by the number of vertices) non-word-representable graph with 6 vertices is the wheel graph $W_{5}$ . Moreover, there are 25 non-word-representable graphs on 7 vertices. Notably, the original list of 25 non-word-representable graphs with 7 vertices, as presented in [6], contains two incorrect graphs. For the corrected catalog of these 25 graphs, we refer the reader to [8].

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_{0} \to v_{1} \to \dots \to v_{k}$ either there is no edge from $v_{0}$ to $v_{k}$ , or $v_{i} \to v_{j}$ is an edge for all $0 \leq i < j \leq k$ . An induced subgraph on at least four vertices ${v_{0}, v_{1}, \dots, v_{k}}$ of an oriented graph is a shortcut if it is acyclic, non-transitive, and contains both the directed path $v_{0} \to v_{1} \to \dots \to v_{k}$ and the edge $v_{0} \to v_{k}$ , that is called the shortcutting edge. A semi-transitive orientation can then be alternatively defined as an acyclic shortcut-free orientation. A fundamental result in the area of word-representable graphs is the following theorem.

Theorem 2.1 ([4]). A graph is word-representable if and only if it admits a semi-transitive orientation.

For instance, it follows from Theorem 2.1 that every 3-colourable graph is word-representable (simply direct each edge from a lower colour to a higher one). In the literature, word-representable graphs are often referred to as semi-transitive graphs.

2.2. $k$ -11-representable graphs

A factor in a word $w_{1} w_{2} \dots w_{n}$ is a word $w_{i} w_{i + 1} \dots w_{j}$ for $1 \leq i \leq j \leq n$ . For any word $w$ , let $π (w)$ be the initial permutation of $w$ obtained by reading $w$ from left to right and recording the leftmost occurrences of the letters in $w$ . Denote by $r (w)$ the reverse of $w$ , that is, $w$ written in the reverse order. Finally, for a pair of letters $x$ and $y$ in a word $w$ , let $w |_{{x, y}}$ be the subword induced by the letters $x$ and $y$ . For example, if $w = 42535214421$ then $π (w) = 42531, r (w) = 12441253524,$ and $w |_{{4, 5}} = 45544$ .

Let $k \geq 0$ . A graph $G = (V, E)$ is $k$ – $11$ -representable if there exists a word $w$ over the alphabet $V$ such that the word $w |_{{x, y}}$ contains in total at most $k$ occurrences of the factors in ${x x, y y}$ if and only if $x y$ is an edge in $E$ . Such a word $w$ is called $G$ ’s $k$ – $11$ -representant. Note that $0$ – $11$ -representable graphs are precisely word-representable graphs, and that $0$ – $11$ -representants are precisely word-representants. A graph $G = (V, E)$ is permutationally $k$ – $11$ -representable if it has a $k$ – $11$ -representant that is a concatenation of permutations of $V$ . The “11” in “ $k$ – $11$ -representable” refers to counting occurrences of the consecutive pattern 11 in the word induced by a pair of letters ${x, y}$ , which is exactly the total number of occurrences of the factors in ${x x, y y}$ .

A uniform (resp., $t$ -uniform) representant of a graph $G$ is a word, satisfying the required properties, in which each letter occurs the same (resp., $t$ ) number of times. It is known that each word-representable graph has a uniform representant [7], the class of 2-uniform representable graphs is exactly the class of circle graphs [6], while the class of $2$ -uniform $1$ – $11$ -representable graphs is the class of interval graphs [2]. The main result in [2] is the following theorem.

Theorem 2.2 ([2]). Every graph $G$ is permutationally $2$ – $11$ -representable.

Thus, when determining whether each graph is $k$ – $11$ -representable for a fixed $k$ , the only case left to study is $k = 1$ (as the answer is no for $k = 0$ and yes for $k \geq 2$ ).

2.3. Known tools to study 1-11-representable graphs

Each word-representable graph is 1-11-representable. Indeed, if $w$ is a word-representant of $G$ then, for instance, $w w$ or $r (π (w)) w$ are its 1-11-representants. Moreover, each graph on at most 7 vertices is 1-11-representable [2,3]. The key tools to study 1-11-representation of graphs from [2,3] can be unified as follows.

Lemma 2.3 ([2]).

(a) Let $G_{1}$ and $G_{2}$ be $1$ – $11$ -representable graphs. Then their disjoint union, glueing them in a vertex or connecting them by an edge results in a $1$ – $11$ -representable graph.

(b) If $G$ is $1$ – $11$ -representable then for any edge $x y$ adding a new vertex adjacent to $x$ and $y$ only, gives a $1$ – $11$ -representable graph.

In the following lemma, $N_{A} (v) = {u \in A ∣ u v \in E (G)}$ .

Lemma 2.4 ([2]). Let $G$ be a word-representable graph, $A \subseteq V$ and $v \in V$ . Then

(a) $G ∖ {x y \in E (G) | x, y \in A}$ is a $1$ – $11$ -representable graph;

(b) $G ∖ {u v \in E (G) | u \in N_{A} (v)}$ is a $1$ – $11$ -representable graph.

In particular, Lemma 2.4(b) is frequently referred to in this paper as the “star operation” or “adding a star”, and it is used as follows: to prove the 1-11-representability of a given graph, we identify a set of new edges, all sharing the same vertex as an endpoint, and demonstrate that the resulting graph is word-representable.

Lemma 2.5 ([2]). Let $G$ be a graph with a vertex $v \in V$ . $G$ is $1$ – $11$ -representable if at least one of the following conditions holds:

(a) $G ∖ v$ is a comparability graph;

(b) $G ∖ v$ is a circle graph.

Lemma 2.6 ([3]).Let $V_{1}, \dots, V_{k}$ be pairwise disjoint subsets of $V$ , the set of vertices of a word-representable graph $G$ . We denote by $E (V_{i})$ the set of all edges of $G$ having both end-points in $V_{i}$ . Then, the graph $H = G ∖ (\cup_{1 \leq i \leq k} E (V_{i}))$ , obtained by removing all edges belonging to $E (V_{i})$ for all $1 \leq i \leq k$ , is $1$ – $11$ -representable.

As a corollary of Lemma 2.6, we obtain the following lemma, which is frequently used in this paper and referred to as “adding a matching” or “applying a matching operation”.

Lemma 2.7 ([3]). Let the graph $G$ be obtained from a graph $H$ by adding a matching (that is, by adding new edges no pair of which shares a vertex). If $G$ is word-representable then $H$ is $1$ – $11$ -representable.

Lemma 2.8 ([3]).Suppose that the vertices of a graph $G$ can be partitioned into a comparability graph formed by vertices in $A = {a_{1}, \dots, a_{k}}$ and an independent set formed by vertices in $B = {b_{1}, \dots, b_{ℓ}}$ . Then $G$ is permutationally $1$ – $11$ -representable.

3. Graphs on at most 8 vertices

In what follows, $χ (G)$ denotes the chromatic number of $G$ . We say that a graph is $(a_{1}, a_{2}, \dots, a_{k})$ -colourable if it can be coloured with $k$ colours, but not with $k - 1$ colours, and the $i$ -th colour class, corresponding to colour $i$ , is the set $V_{i} = {v_{i}, v_{i}^{'}, v_{i}^{″}, \dots}$ of size $a_{i}$ . Our typical assumption, w.l.o.g., is that $a_{1} \geq a_{2} \geq \dots \geq a_{k}$ . However, in certain cases, we deviate from this assumption to be able to facilitate our arguments.

Remark 3.1. It is easy to see that the induced subgraph $G [\cup_{a_{i} = 1} V_{i}]$ is a clique.

Definition 3.2. A $(b_{1} b_{2} \dots b_{m})$ -shortcut is a shortcut with the directed path $w_{b_{1}} \to w_{b_{2}} \to \dots \to w_{b_{m}}$ , where $w_{b_{i}} \in V_{i}$ for $1 \leq i \leq m$ . A $(b_{1} b_{2} \dots b_{s}$ –)-shortcut is any $(c_{1} c_{2} \dots c_{t})$ -shortcut such that $b_{i} = c_{i},$ for $i \in {1, 2 \dots, s}$ , and $t \geq s$ .

For sets of vertices $X$ and $Y$ in a graph, let $e (X, Y)$ denote the number of (directed or undirected) edges between $X$ and $Y$ . For brevity, a singleton set ${x}$ is denoted as $x$ . Additionally, for a graph $G$ with disjoint subsets of vertices $V_{1}, \dots, V_{m}$ , where $V_{i}$ is an independent set for $1 \leq i \leq m$ , let $G [V_{1}, \dots, V_{m}]$ represent the induced $m$ -partite subgraph of $G$ on the vertices in $\cup_{1 \leq i \leq m} V_{i}$ . Finally, a split graph is a graph whose vertex set can be partitioned into a comparability graph and an independent set.

Lemma 3.3. If a graph $G$ is $(k, 1, 1, \dots, 1)$ -colourable, then $G$ is $1$ – $11$ -representable.

Proof. Clearly, $G$ is a split graph with an independent set of size $k$ , and by Theorem 6 in [3], any split graph is permutationally 1-11-representable.

Lemma 3.4. For an $(a_{1}, a_{2}, \dots, a_{k})$ -colourable graph $G$ , where $a_{1} \geq a_{2} \geq \dots \geq a_{i} > a_{i + 1} = a_{i + 2} = \dots = a_{k} = 1$ , if $e (V_{s}, V_{t}) = 1$ for some $s \leq i < t$ , then the vertex in $V_{t}$ and its unique neighbour in $V_{s}$ are adjacent to all vertices in $V_{j}$ for $j > i$ .

Proof. Assume that $V_{t} = {v_{t}}$ is adjacent to a vertex $v_{s} \in V_{s}$ . Since $a_{t} = 1$ , by Remark 3.1, the claim holds for $v_{t}$ . Now, suppose that $v_{s}$ is not adjacent to some $v_{ℓ} \in V_{ℓ}$ for $ℓ > i$ . By recolouring the vertices in $V_{s} ∖ {v_{s}}$ in colour $t$ and the vertex $v_{s}$ in colour $ℓ$ , we obtain a $(k - 1)$ -colouring of $G$ , which contradicts the assumption that $χ (G) = k$ . Therefore, $v_{s}$ must be adjacent to all vertices in $V_{j}$ for $j > i$ .

The proof of the following theorem can be reduced to considering the 929 non-word-representable graphs on 8 vertices ([6, p. 47]) since any word-representable graph is 1-11-representable. Our final Section 5 contains an intriguing question about this. However, our arguments are not restricted to the 929 graphs – we consider all graphs on 8 vertices based on their chromatic number and prove their 1-11-representability.

Theorem 3.5. All graphs on at most $8$ vertices are $1$ – $11$ -representable.

Proof. We begin with the easier cases and continue with the more involved ones.

Case 1. $χ (G) \leq 3$ . Any such graph is word-representable and hence 1-11-representable.

Case 2. $χ (G) = 8$ . This is a complete graph which is word-representable and hence 1-11-representable.

Case 3. $χ (G) = 7$ . By Lemma 3.3, $G$ is word-representable, and hence 1-11-representable.

Our strategy for the remainder of the proof is to consider a suitable $(a_{1}, a_{2}, \dots, a_{k})$ -colouring of $G$ . We then orient edges $u v$ , where $u \in V_{i}$ and $v \in V_{j}$ with $i < j$ , as $u \to v$ . Next, we apply a star or a matching operation to add additional edges, oriented again from smaller colour to larger colours, to eliminate potential shortcuts. This process ensures a semi-transitive orientation, demonstrating that the resulting graph is word-representable and, consequently, that the original graph is 1-11-representable.

Case 4. $χ (G) = 6$ . Then $G$ is either $(3, 1, 1, 1, 1, 1)$ -colourable or $(2, 2, 1, 1, 1, 1)$ -colourable. By Lemma 3.3, we can assume that $G$ is $(2, 2, 1, 1, 1, 1)$ -colourable, with its vertices coloured as shown in the picture below. No edges are drawn in the picture (as is the case with all the pictures below), and, in particular, the vertices in $C = {v_{3}, v_{4}, v_{5}, v_{6}}$ form a clique. In the picture, colours $1$ to $6$ correspond to red, blue, green, orange, yellow, and black, respectively.

Suppose that $v_{1}$ is not adjacent to a vertex in $C$ . W.l.o.g., assume that $v_{1} v_{3}$ is not an edge. Clearly, $v_{1}^{'} v_{3}$ is an edge; otherwise, $v_{3}$ can be coloured red, contradicting $χ (G) = 6$ . But then, by Lemma 3.4, $v_{1}^{'}$ is adjacent to every vertex in $C$ .

The considerations above can also be applied to $v_{2}$ and $v_{2}^{'}$ instead of $v_{1}$ and $v_{1}^{'}$ . By renaming $v_{1}$ (resp., $v_{2}$ ) and $v_{1}^{'}$ (resp., $v_{2}^{'}$ ), if necessary, we can assume that both $v_{1}$ and $v_{2}$ are adjacent to all vertices in $C$ . Add any missing edges between $v_{1}^{'}$ and the vertices in $C$ to obtain a graph $G^{'}$ , and rename the vertices in $C$ , if necessary, so that the neighbours of $v_{2}^{'}$ in $C$ are in the set $C^{'} = {v_{i}, v_{i + 1}, \dots, v_{6}}$ for $3 \leq i \leq 7$ (note that $C^{'}$ may be empty). Finally, orient the edges in $G^{'}$ as $v_{i} \to v_{j}$ and $v_{i}^{'} \to v_{j}$ , for $1 \leq i < j \leq 6$ , and $v_{1} \to v_{2}^{'}$ and $v_{1}^{'} \to v_{2}^{'}$ (if any of these edges exists). It is easy to check that the obtained orientation is semi-transitive (in fact, transitive), so by Theorem 2.1, $G^{'}$ is word-representable, and by Lemma 2.4(b), $G$ is 1-11-representable.
Case 5. $χ (G) = 5$ . The only possible shortcuts in this graph are (12345)-, (1234)-, (1235)-, (1245)-, (1345)-, or (2345)-shortcuts and possible missing edges appear only in $G [V_{1}, V_{3}]$ , $G [V_{1}, V_{4}]$ , $G [V_{2}, V_{4}]$ , $G [V_{2}, V_{5}]$ , $G [V_{3}, V_{5}]$ .

$G$ is $(4, 1, 1, 1, 1)$ -, $(3, 2, 1, 1, 1)$ -, or $(2, 2, 2, 1, 1)$ -colourable. By Lemma 3.3, we can assume that $G$ is not $(4, 1, 1, 1, 1)$ -colourable.

If $G$ is $(2, 1, 1, 1, 3)$ -colourable as in the picture below, which is equivalent to $G$ being $(3, 2, 1, 1, 1)$ -colourable, then $G [{v_{2}, v_{3}, v_{4}}]$ is a triangle; $e (V_{i}, v_{j}) \geq 1$ for $i = 1, 5$ and $j = 2, 3, 4$ or else we can recolour some vertex in ${v_{2}, v_{3}, v_{4}}$ and obtain a 4-colouring of $G$ , which is impossible; $e (v_{1}, V_{5}) \geq 1$ and $e (v_{1}^{'}, V_{5}) \geq 1$ , and hence $e (V_{1}, V_{5}) \geq 2$ , or we can recolour some vertices and get a (4,1,1,1,1)-colouring.

We first prove the following fact, which will be used multiple times below: if there are at least two vertices among $v_{2}, v_{3}, v_{4}$ that have only one neighbour in $V_{5}$ , then $G$ is 1-11-representable. W.l.o.g., we assume $e (v_{3}, V_{5}) = e (v_{4}, V_{5}) = 1$ and $v_{3} v_{5} \in E (G)$ . By Lemma 3.4, $v_{5}$ is adjacent to $v_{2}$ , $v_{3}$ , and $v_{4}$ . Now, by adding all edges in $G [V_{1}, v_{3}]$ and $G [V_{1}, v_{4}]$ , we add at most two edges, which can only result from applying a star or matching operation. By Lemma 2.4 or Lemma 2.7, we claim that there is no shortcut now, so the original graph $G$ is 1-11-representable. Indeed, possible (12345)-, (1345)-, (1235)-, (1245)-, or (2345)-shortcuts must end with edge $v_{3} v_{5}$ or $v_{4} v_{5}$ , but $G [V_{1}, V_{3}]$ , $G [V_{1}, V_{4}]$ , and $G [V_{2}, V_{4}]$ are complete bipartite and $v_{2} v_{5}, v_{3} v_{5} \in E (G)$ . Moreover, (1234)-shortcuts do not exist because $G [V_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ are complete bipartite. Therefore, the orientation is indeed semi-transitive, and $G$ is indeed 1-11-representable. Hence, in the rest of the proof, we may assume that there are at least two vertices among $v_{2}, v_{3}, v_{4}$ that have more than one neighbours in $V_{5}$ .

Now, let us discuss the different cases based on the possible values of $e (V_{1}, v_{i})$ , where $i \in {2, 3, 4}$ . Consider the multiset ${e (V_{1}, v_{i}) | i \in {2, 3, 4}}$ . Let $κ$ be the number of occurrences of 1 in this multiset. We consider four cases.

i) $κ = 0$ , which means $e (V_{1}, v_{i}) = 2$ for $i = 2, 3, 4$ . We can assume that $e (v_{2}, V_{5}) = e (V_{2}, V_{5}) \geq 2$ and $e (v_{3}, V_{5}) = e (V_{3}, V_{5}) \geq 2$ as stated before. By adding at most two edges we can make $G [V_{2}, V_{5}]$ and $G [V_{3}, V_{5}]$ complete bipartite. Note that $G [V_{1}, V_{3}]$ , $G [V_{1}, V_{4}]$ , and $G [V_{2}, V_{4}]$ are already complete bipartite, so there is no shortcut in the above orientation and $G$ is 1-11-representable.

ii) $κ = 1$ . By recolouring $v_{3}, v_{4}, v_{5}$ , if necessary, we can assume that $e (V_{1}, v_{2}) = 1$ , $e (V_{1}, v_{3}) = 2$ , $e (V_{1}, v_{4}) = 2$ and $v_{1} v_{2} \in E (G)$ . By symmetry, we can assume that $e (v_{2}, V_{5}) \geq e (v_{1}, V_{5})$ (if not, swap $v_{1}$ and $v_{2}$ ). We can add to $G$ , by a matching or star operation, edge $v_{2} v_{5}$ (resp., $v_{2} v_{5}^{'}$ , $v_{2} v_{5}^{″}$ ) if $v_{1} v_{5}$ (resp., $v_{1} v_{5}^{'}$ , $v_{1} v_{5}^{″}$ ) is an edge in $E$ , and edges ${v_{3} v_{5}, v_{3} v_{5}^{'}, v_{3} v_{5}^{″}}$ . In fact, we need to add at most two edges because $e (v_{2}, V_{5}) \geq e (v_{1}, V_{5})$ and $e (v_{3}, V_{5}) \geq 2$ . We claim that then there is no shortcut in the above orientation: (12–)-shortcuts must start with $v_{1} v_{2}$ , but $N_{V_{5}} (v_{1}) \subseteq N_{V_{5}} (v_{2})$ and $G [v_{1}, V_{3}]$ , $G [v_{1}, V_{4}]$ , $G [V_{2}, V_{4}]$ , and $G [V_{3}, V_{5}]$ are complete bipartite so there is no such shortcut; (1345), (2345)-shortcuts do not exist because $G [V_{1}, V_{4}]$ , $G [V_{3}, V_{5}]$ , and $G [V_{2}, V_{4}]$ are complete bipartite.

iii) $κ = 2$ . By recolouring $v_{3}, v_{4}, v_{5}$ , if necessary, we can assume that $e (V_{1}, v_{2}) = 1, e (V_{1}, v_{3}) = 1, e (V_{1}, v_{4}) = 2$ . Note that earlier we assumed that there are at least two vertices among $v_{2}, v_{3}, v_{4}$ that have more than one neighbour in $V_{5}$ . Therefore, by symmetry, we can further assume that $e (v_{3}, V_{5}) \geq 2.$

Similarly to the above, we assume that $v_{1} v_{2} \in E (G)$ then $v_{1} v_{3}, v_{1} v_{4} \in E (G)$ . By symmetry, we assume that $e (v_{2}, V_{5}) \geq e (v_{1}, V_{5})$ . We can add at most one edge to ensure $N_{V_{5}} (v_{1}) \subseteq N_{V_{5}} (v_{2})$ , and then add at most one additional edge to ensure that $G [V_{3}, V_{5}]$ is complete bipartite. Now there is no shortcut.

iv) $κ = 3$ , which means that $e (V_{1}, v_{i}) = 1$ for $i = 2, 3, 4$ . We assume $v_{1} v_{2} \in E (G)$ then $v_{1} v_{3}, v_{1} v_{4} \in E (G)$ . By symmetry, we assume $e (v_{2}, V_{5}) \geq e (v_{1}, V_{5})$ . Using the same method as in Case iii), we get a semi-transitive orientation by adding at most 2 edges, which means $G$ is 1-11-representable.

If $G$ is $(2, 1, 1, 2, 2)$ -colourable as shown in the picture below, we can assume that $G [V_{1}, V_{4}]$ , $G [V_{1}, V_{5}]$ , and $G [V_{4}, V_{5}]$ all have perfect matchings. Otherwise, we can recolour some vertices to obtain a $(3, 2, 1, 1, 1)$ -colouring.

For $i \in {2, 3}$ , let $f (i) = (e (V_{1}, v_{i}), e (v_{i}, V_{4}), e (v_{i}, V_{5}))$ . Then $f (i) \in {1, 2}^{3}$ .

First we assume that there are different $s, t \in {1, 4, 5}$ , such that $e (V_{s}, v_{2}) = e (V_{t}, v_{2}) = e (V_{s}, v_{3}) = e (V_{t}, v_{3}) = 1$ . By symmetry we can assume $s = 1$ , $t = 4$ . That is, $e (V_{1}, v_{2}) = e (V_{1}, v_{3}) = e (v_{2}, V_{4}) = e (v_{3}, V_{4}) = 1$ . By Lemma 3.4, we can assume that $v_{1} v_{2}, v_{1} v_{3}, v_{2} v_{4}, v_{3} v_{4} \in E (G)$ . Now we see that $v_{1} v_{4} \in E (G)$ , or we can recolour $v_{1}$ and $v_{4}$ green, recolour $v_{2}$ red, recolour $v_{3}$ yellow and get a 4-colouring, contradiction. By adding at most two edges we can make $G [V_{2}, V_{5}]$ and $G [V_{3}, V_{5}]$ complete bipartite. We claim that then there is no shortcut in the above orientation and the original is 1-11-representable. Indeed, (1–)-shortcuts must start from $v_{1} v_{2} \to v_{2} v_{3} \to v_{3} v_{4}$ , $v_{1} v_{3} \to v_{3} v_{4}$ or $v_{1} v_{2} \to v_{2} v_{4}$ , but $v_{1} v_{3}, v_{1} v_{4}, v_{2} v_{4} \in G$ , $N_{V_{4}} (v_{3}) = {v_{4}} \subseteq N_{V_{4}} (v_{1})$ and $G [V_{2}, V_{5}]$ and $G [V_{3}, V_{5}]$ are complete bipartite, so no such shortcut exists.

Let $k_{i}$ be the number of 2 in the triple $f (i)$ for $i = 2, 3$ . Now, let us discuss the different cases based on the possible values of $κ = max {k_{1}, k_{2}}$ . First note that $κ \geq 1$ , otherwise we can find two different $s, t \in {1, 4, 5}$ , such that $e (V_{s}, v_{2}) = e (V_{t}, v_{2}) = e (V_{s}, v_{3}) = e (V_{t}, v_{3}) = 1$ .

i) $κ = 3$ and $f (i) \neq (1, 1, 1)$ for $i = 2, 3$ . Then by symmetry we can assume $e (v_{2}, V_{4}) = e (v_{2}, V_{5}) = e (v_{3}, V_{1}) = 2$ . Then we can add a matching to make $G [V_{1}, V_{4}]$ and $G [V_{3}, V_{5}]$ complete bipartite. But $G [V_{1}, V_{3}]$ , $G [V_{2}, V_{4}]$ , and $G [V_{2}, V_{5}]$ are already complete bipartite, so there is no shortcut in the above orientation and the original graph is 1-11-representable.

ii) $κ = 2$ . By symmetry we can assume $e (V_{1}, v_{2}) = 1$ , $e (v_{2}, V_{4}) = e (v_{3}, V_{5}) = 2$ . By Lemma 3.4, we can assume $v_{1} v_{2}, v_{1} v_{3} \in E (G)$ . After adding all edges in $G [V_{1}, V_{4}]$ we add at most a matching or we can recolour some vertices and get a (3,2,1,1,1)-colouring or a 4-colouring. We claim that then there is no shortcut in the above orientation and the original is 1-11-representable: $G [V_{1}, V_{4}]$ , $G [V_{3}, V_{5}]$ , $G [V_{2}, V_{4}]$ , and $G [V_{2}, V_{5}]$ are complete bipartite, and shortcuts $G [V_{1}, V_{3}]$ are (123–)-shortcuts, which starts from $v_{1} v_{2}$ , $v_{2} v_{3}$ , but $v_{1} v_{3} \in E (G)$ so no such shortcut exists.

iii) $κ = 1$ . By the above discussion, there are no different $s, t \in {1, 4, 5}$ , such that $e (V_{s}, v_{2}) = e (V_{t}, v_{3}) = e (V_{s}, v_{2}) = e (V_{t}, v_{3}) = 1$ . Thus by symmetry, we can assume that $e (V_{1}, v_{2}) = e (v_{2}, V_{4}) = e (v_{3}, V_{4}) = e (v_{3}, V_{5}) = 1$ and $e (v_{2}, V_{5}) = e (V_{1}, v_{3}) = 2$ . Then also by symmetry and Lemma 3.4 we can assume that $v_{1} v_{2}, v_{2} v_{4}, v_{3} v_{4}, v_{3} v_{5} \in E (G)$ . By adding at most a matching (or we can get a (3,2,1,1,1)-colouring or a 4 colouring) we can make $G [V_{1}, V_{4}]$ and $G [V_{3}, V_{5}]$ complete bipartite. We claim that then there is no shortcut in the above orientation and the original graph is 1-11-representable: (12–)-shortcuts must start from $v_{1} v_{2} \to v_{2} v_{3} \to v_{3} v_{4}$ or $v_{1} v_{2} \to v_{2} v_{4}$ , but $v_{1} v_{3}, v_{2} v_{4} \in E (G)$ and $G [V_{1}, V_{4}]$ , $G [V_{2}, V_{5}]$ , and $G [V_{3}, V_{5}]$ are complete bipartite, so no such shortcut exists; (1345)-shortcuts do not exist because $G [V_{1}, V_{4}]$ and $G [V_{3}, V_{5}]$ are complete; (2345)-shortcuts must start from $v_{2} v_{3} \to v_{3} v_{4}$ , and so it’s easy to see that no such shortcuts exists.

iv) The only remained case is that $κ = 3$ , but there is some $i \in {2, 3}$ , such that $f (i) = (1, 1, 1)$ . By symmetry, we can assume $e (v_{2}, V_{i}) = 1, e (v_{3}, V_{i}) = 2$ for $i \in {1, 4, 5}$ . Further, by symmetry we can assume $v_{1} v_{2}, v_{2} v_{4}, v_{2} v_{5} \in E (G)$ .

We claim that $e (v_{1}, V_{4}) = e (v_{1}, V_{5}) = e (v_{4}, V_{1}) = e (v_{4}, V_{5}) = e (v_{5} . V_{1}) = e (v_{5}, V_{4}) = 1$ . Otherwise, for example, $e (v_{1}, V_{4}) = 2$ . Then we can change the colour of $v_{i}$ and $v_{2}$ to get a new $(2, 1, 1, 2, 2)$ -colouring. In this colouring, the triples $f (2), f (3)$ satisfy the condition we have discussed before.

Again, we claim that $G [{v_{1}, v_{4}, v_{5}}]$ is not the empty graph. Otherwise we recolour $v_{1}, v_{4}, v_{5}$ red and recolour $v_{1}^{'}, v_{2}$ green, and we get a (3,2,1,1,1)-colouring. Without loss of generality, we can assume $v_{1} v_{5} \in E (G)$ . Since $e (v_{1}, V_{5}) = e (v_{5}, V_{1}) = 1$ , we see that $v_{1} v_{5}^{'}, v_{1}^{'} v_{5} \notin E (G)$ . Then we can change the colour of $v_{1}, v_{5}$ and get a new $(2, 1, 1, 2, 2)$ -colouring. In this colouring, the triples $f (2), f (3)$ again satisfy the condition we have discussed before.

Case 6. $χ (G) = 4$ . The only shortcuts in this graph are only (1234)-shortcuts and possible missing edges appear only in $G [V_{1}, V_{3}], G [V_{2}, V_{4}]$ .

If $G$ is $(5, 1, 1, 1)$ -colourable then, by Lemma 3.3, $G$ is 1-11-representable.

If $G$ is $(4, 2, 1, 1)$ -colourable as in the picture below, we can assume $e (V_{2}, v_{3}) \leq e (V_{2}, v_{4})$ by symmetry. If $e (V_{2}, v_{4}) = 2$ , we can add all edges in $G [V_{1}, v_{3}]$ by adding at most a star subgraph. Then $G [V_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ are complete bipartite and there is no shortcut in the above orientation. So the original graph is 1-11-representable. If $e (V_{2}, v_{3}) = e (V_{2}, v_{4}) = 1$ , by Lemma 3.4, we can assume $v_{2} v_{3}, v_{2} v_{4} \in E (G)$ . Then still we add all edges in $G [V_{1}, v_{3}]$ by adding at most a star subgraph and there is no shortcut in the above orientation. Indeed, a (1234)-shortcut must end with $v_{2} v_{3}$ and $v_{3} v_{4}$ , but $G [V_{1}, V_{3}]$ and $G [v_{2}, V_{4}]$ are complete bipartite, which is a contradiction. So, the original graph is 1-11-representable.

If $G$ is $(3, 3, 1, 1)$ -colourable as in the picture below, we see that $e (V_{i}, V_{j}) \geq 1$ for $i \in {1, 2}, j \in {3, 4}$ . If $e (V_{2}, v_{3}) = 1$ , by Lemma 3.4 we can assume $v_{2} v_{3}, v_{2} v_{4} \in E (G)$ . We can add all edges in $G [V_{1}, v_{3}]$ by adding at most a star subgraph and there is no shortcut in the above orientation. Indeed, a (1234)-shortcut must end with $v_{2} v_{3}$ and $v_{3} v_{4}$ , but $G [V_{1}, V_{3}]$ and $G [v_{2}, V_{4}]$ are complete bipartite, which is a contradiction. So the original graph is 1-11-representable. Now by symmetry we can assume $e (V_{i}, V_{j}) \geq 2$ for $i \in {1, 2}$ , $j \in {3, 4}$ . Then, by adding at most two edges we can make $G [V_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ complete bipartite and there is no shortcut in the above orientation. So the original graph is 1-11-representable.

If $G$ is $(3, 2, 1, 2)$ -colourable as in the picture below, we can assume that $G$ is not $(3, 3, 1, 1)$ -colourable, so we can add a matching into $G [V_{2}, V_{4}]$ to make it a complete bipartite graph. If $e (V_{1}, v_{3}) \geq 2$ , then we can add a matching into $G$ to make $G [V_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ complete bipartite graphs and then there is no shortcut under the above orientation, and so the original graph is 1-11-representable.

Thus, we see that $e (V_{1}, v_{3}) = 1$ . Then by swapping $V_{2}$ and $V_{3}$ we can assume $E (V_{1}, V_{2}) = {v_{1} v_{2}}$ as in the picture below. Note that $e (v_{2}, V_{3}) \geq 1$ , so by colouring $v_{1}$ green and colouring $v_{2}$ red (it is still a proper colouring), we can assume $e (v_{1}, V_{3}) \geq 1$ . In this case, we can add a matching into $G$ to make $G [v_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ complete bipartite graphs and then there is no shortcut under the above orientation: (1234)-shortcuts must start with $v_{1} v_{2}$ , but $G [v_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ are complete bipartite. So the original graph is 1-11-representable.

If $G$ is $(2, 2, 2, 2)$ -colourable as in the picture below, we can assume that $G$ is not $(3, 2, 2, 1)$ -colourable. Note that for any $1 \leq i < j \leq 4$ , we can add a matching to make $G [V_{i}, V_{j}]$ a complete bipartite graph, otherwise, there is a vertex $v \in V_{i} \cup V_{j}$ with no edge in $G [V_{i}, V_{j}]$ . Then we can assume $v \in V_{i}$ and recolour it with the colour of $V_{j}$ , thereby obtaining a $(3, 2, 2, 1)$ -colouring. Thus, we can add a matching into $G$ to make $G [V_{1}, V_{3}]$ and $G [V_{2}, V_{4}]$ complete bipartite graphs. By adding this vertex to the component, we will get a $(3, 2, 2, 1)$ -colouring, contradiction. Thus there is no shortcut under the above orientation, and so $G$ is 1-11-representable.

All cases have been considered; thus, the theorem is proved.

4. Multi-1-11-representation number of a graph

In this section, we generalize and extend the notion of the multi-word-representation number of a graph, introduced in [5] by Kenkireth and Malhotra. The key idea involves using multiple words over the same alphabet to represent different graphs, and declaring that the union of these word-representants represents the union of graphs.

Definition 4.1. Suppose that the graphs $G_{1}, G_{2}, \dots, G_{m}$ share the same vertex set, i.e., $V (G_{1}) = \dots = V (G_{m}) = V$ and that the graphs $G$ and $G^{'}$ satisfy the following:

$∙$ $V (G) = V$ and $E (G) = \cup_{1 \leq i \leq m} E (G_{i})$ ;

$∙$ $V (G^{'}) = V$ , $E (G^{'}) = \cup_{1 \leq i \leq m} E (G_{i})$ , and $E (G_{i}) \cap E (G_{j}) = \emptyset$ for $1 \leq i < j \leq m$ .

Further assume that each $G_{i}$ , $1 \leq i \leq m$ , is $k$ -11-representable, and that $m$ is minimal possible value for $G$ and $G^{'}$ . Then, we define the (resp., strict) multi- $k$ – $11$ -representation number of $G$ (resp., $G^{'}$ ) to be $m$ .

Note that, according to our terminology, the multi-word-representation number in [5] is precisely the multi-0-11-representation number. Also, the strict version of the “multi-word representation number” is introduced by us for the first time.

Since each graph is $k$ -11-representable for $k \geq 2$ (see [2]), the (strict) multi- $k$ -11-representation number of such a graph is 1. Hence, Definition 4.1 is meaningful only in the case $k \in {0, 1}$ . In particular, unless it is proven that all graphs are 1-11-representable, establishing the (strict) multi- $k$ -11-representation number for graphs, or classes of graphs, remains an interesting and challenging problem. Furthermore, note that the multi-1-11-representation number is clearly at most equal to the strict multi-1-11-representation number.

Using the approach in [5] and applying our results from Section 3, we can prove the following theorem.

Theorem 4.2. All graphs on at most $24$ vertices have a strict multi- $1$ – $11$ -representation number of at most $2$ .

Proof. Suppose $G$ is a graph on 24 vertices (for smaller graphs, the statement will follow by the hereditary nature of 1-11-representation). Consider an arbitrary partition of $V (G)$ into three disjoint subsets $V_{1}$ , $V_{2}$ , and $V_{3}$ , each containing 8 vertices. By Theorem 3.5, the graph $G [V_{i}]$ , $i \in {1, 2, 3}$ , is 1-11-representable. Furthermore, by Lemma 2.3(a), the graph $G^{'} := G [V_{1}] \cup G [V_{2}] \cup G [V_{3}]$ can be 1-11-represented by a word $w_{1}$ .

Next, removing all edges within $G [V_{1}]$ , $G [V_{2}]$ , and $G [V_{3}]$ from $G$ , we obtain a 3-colourable graph $G^{″}$ , which is word-representable and therefore 1-11-representable [2]. Thus, we can find a word $w_{2}$ that 1-11-represents $G^{″}$ .

Since $V (G) = V (G^{'}) = V (G^{″})$ , $E (G) = E (G^{'}) \cup E (G^{″})$ , and $E (G^{'}) \cap E (G^{″}) = \emptyset$ , the strict 1-11-representation number of $G$ is at most 2.

5. Concluding remarks

We conclude this paper with several open directions for future research:

$∙$ Are all 4-colourable graphs 1-11-representable? If this is the case, the result of Theorem 4.2 could be immediately improved by replacing 24 with 32. Indeed, in the proof of that theorem, we could partition the vertex set of $G$ into four sets, each containing 8 vertices, and use the 1-11-representability of the 4-colourable $G^{″}$ .

$∙$ If proving or disproving that all 4-colourable graphs are 1-11-representable proves too challenging, one could instead address the same question for all planar graphs, a subclass of 4-colourable graphs.

$∙$ Assuming that proving or disproving that any graph is 1-11-representable remains infeasible with existing tools, one could focus on proving or disproving that the (strict) multi-1-11-representation number of any graph is at most 2. This question is likely easier, at least for various classes of graphs, than proving 1-11-representability. It should also be more tractable than resolving the open problem of whether the multi-word-representation number of any graph is at most 2 (since graphs can be modified by adding edges).

$∙$ The notions of strict and non-strict multi- $k$ -11-representation numbers are equivalent for $k \geq 2$ . What can be said about $k \in 0, 1$ ? Is it possible to construct any counterexamples in this case?

$∙$ Definition 4.1 can, in fact, be refined to the $ℓ$ -multi- $k$ -11-representation number, where any edge can belong to at most $ℓ$ subgraphs. In this framework, the strict multi- $k$ -11-representation corresponds to the case $ℓ = 1$ . Could such a refinement lead to interesting results for $k = 0$ (word-representation) or $k = 1$ (assuming not all graphs are 1-11-representable)?

$∙$ Finally, Herman Chen’s experiments [1] suggest that the 1-11-representability of graphs on 8 vertices can be established by adding at most one new edge (each of the 929 non-word-representable graphs can be converted into a word-representable graph by adding a single edge). However, our arguments in Section 3 often rely on adding more than one edge. Is it possible to prove (not computationally) that adding at most one edge is sufficient? Such a proof could lead to useful techniques, for example, to establish the 1-11-representability of all graphs with 9 vertices (if they are indeed 1-11-representable).

Acknowledgments

The authors are grateful to Brian Ritchie and Hehui Wu for their useful discussions related to the paper. Additionally, the authors would like to thank the anonymous referee for providing many helpful comments that improved the presentation.

References:

H. Z. Q. Chen. Private communication, 2024.
G.-S. Cheon, J. Kim, M. Kim, S. Kitaev, and A. Pyatkin. On k-11-representable graphs. Journal of Combinatorics, 10(3):491–513, 2019. https://doi.org/10.4310/JOC.2019.v10.n3.a3.
M. Etorny, S. Kitaev, and A. Pyatkin. New tools to study 1-11-representation of graphs. Graphs and Combinatorics, 40(5):Paper No. 97, 13, 2024. https://doi.org/10.1007/s00373-024-02825-1.
M. M. Halldórsson, S. Kitaev, and A. Pyatkin. Semi-transitive orientations and word-representable graphs. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 201:164–171, 2016. https://doi.org/10.1016/j.dam.2015.07.033.
B. G. Kenkireth and A. S. Malhotra. On word-representable and multi-word-representable graphs. In Developments in Language Theory, Volume 13911, Lecture Notes in Comput. Sci., pages 156–167. Springer, Cham, [2023] ©2023. https://doi.org/10.1007/978-3-031-33264-7_13.
S. Kitaev and V. Lozin. Words and Graphs. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015, pages xviii+264. https://doi.org/10.1007/978-3-319-25859-1. With a foreword by Martin Charles Golumbic.
S. Kitaev and A. Pyatkin. On representable graphs. Journal of Automata, Languages and Combinatorics, 13(1):45–54, 2008.
S. Kitaev and H. Sun. Human-verifiable proofs in the theory of word-representable graphs. RAIRO Theoretical Informatics and Applications (RAIRO: ITA), 58:Paper No. 9, 10, 2024. https://doi.org/10.1051/ita/2024004.
J. P. Spinrad. Efficient Graph Representations. Fields Institute Monographs, 19:1–342, 2003. https://doi.org/10.1090/fim/019.

[1] H. Z. Q. Chen. Private communication, 2024.

[2] G.-S. Cheon, J. Kim, M. Kim, S. Kitaev, and A. Pyatkin. On k-11-representable graphs. Journal of Combinatorics, 10(3):491–513, 2019. https://doi.org/10.4310/JOC.2019.v10.n3.a3.

[3] M. Etorny, S. Kitaev, and A. Pyatkin. New tools to study 1-11-representation of graphs. Graphs and Combinatorics, 40(5):Paper No. 97, 13, 2024. https://doi.org/10.1007/s00373-024-02825-1.

[4] M. M. Halldórsson, S. Kitaev, and A. Pyatkin. Semi-transitive orientations and word-representable graphs. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 201:164–171, 2016. https://doi.org/10.1016/j.dam.2015.07.033.

[5] B. G. Kenkireth and A. S. Malhotra. On word-representable and multi-word-representable graphs. In Developments in Language Theory, Volume 13911, Lecture Notes in Comput. Sci., pages 156–167. Springer, Cham, [2023] ©2023. https://doi.org/10.1007/978-3-031-33264-7_13.

[6] S. Kitaev and V. Lozin. Words and Graphs. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015, pages xviii+264. https://doi.org/10.1007/978-3-319-25859-1. With a foreword by Martin Charles Golumbic.

[7] S. Kitaev and A. Pyatkin. On representable graphs. Journal of Automata, Languages and Combinatorics, 13(1):45–54, 2008.

[8] S. Kitaev and H. Sun. Human-verifiable proofs in the theory of word-representable graphs. RAIRO Theoretical Informatics and Applications (RAIRO: ITA), 58:Paper No. 9, 10, 2024. https://doi.org/10.1051/ita/2024004.

[9] J. P. Spinrad. Efficient Graph Representations. Fields Institute Monographs, 19:1–342, 2003. https://doi.org/10.1090/fim/019.

Contents

Utilitas Mathematica