Letter Graphs and Well-Quasi-Order by Induced Subgraphs

Marko Petkovšek Faculty of Mathematics and Physics Department of Mathematics and Mechanics University of Ljubljana, Slovenia

Abstract

Given a word w over a finite alphabet and a set of ordered pairs of letters which define adjacencies, we construct a graph which we call the letter graph of w. The lettericity of a graph G is the least size of alphabet permitting to obtain G as a letter graph. The set of 2-letter graphs consists of threshold graphs, unbounded-interval graphs, and their complements. We determine the lettericity of cycles and bound the lettericity of paths to an interval of length one. We show that the class of k-letter graphs is well-quasi-ordered by the induced subgraph relation, and that it has a finite set of minimal forbidden induced subgraphs. As a consequence, k-letter graphs can be recognized in polynomial time for any fixed k.

1 Introduction

In graph theory, a reflexive and transitive relation is called a quasi-order. A quasi-order ≤ on X is a well-quasi-order if for any infinite sequence a_{1}, a_{2}, … ∈ X there are indices i < j such that a_{i} ≤ a_{j}. Equivalently, X contains no infinite strictly decreasing sequences and no infinite antichains. Yet another equivalent characterization of well-quasi-orders is that every nonempty subset of X has a nonzero finite number of minimal elements (cf. [9, 12]).

By the famous Graph Minor Theorem of N. Robertson and P. D. Seymour, the graph minor relation is a well-quasi-order on the class of all graphs. This, however, is not true for the more restrictive relations such as the topological minor (or homeomorphic embeddability), the subgraph, and the induced subgraph relations. It is therefore of interest to identify restricted classes of graphs which are well-quasi-ordered by these relations. For example, the class of all trees is well-quasi-ordered by the topological minor relation, according to a well-known theorem of J. B. Kruskal [11]. G. Ding has proved that a subgraph ideal (i.e., a class of graphs closed under taking subgraphs) is well-quasi-ordered by the subgraph relation if and only if it contains at most finitely many graphs C_{n} and F_{n} (C_{n} being the cycle on n vertices, and F_{n} the path on n vertices with two pendant edges attached to each of its endpoints).

Concerning the induced subgraph relation ≤_{i} that we shall consider here, the following is known. P. Damaschke [3] has proved that P_{4}-reducible graphs (i.e., graphs in which all induced paths on four vertices are vertex-disjoint) are well-quasi-ordered by ≤_{i}. G. Ding has proved that the following classes of graphs are well-quasi-ordered by ≤_{i}:

• G_{r}, the class of graphs G such that for some R ⊆ V (G) with |R| ≤ r, the graph G − R has matroidal number at most three [6],

• any subgraph ideal which is well-quasi-ordered by the subgraph relation [5].

In [3] and [5], several further classes of graphs defined by excluding a finite set of forbidden induced subgraphs have been shown well-quasi-ordered by ≤_{i}.

In this paper we present another family of induced-subgraph ideals which are well-quasi-ordered by ≤_{i}. Given a word w over a finite alphabet and a set of ordered pairs of letters which define adjacencies, we construct a graph which we call the letter graph of w. The lettericity of a graph G is the least size of alphabet permitting to obtain G as a letter graph. In Section 3 we state some basic properties of k-letter graphs. The class of 2-letter graphs is described completely in Section 4: it is composed of threshold graphs, unbounded-interval graphs, and their complements. In Section 5 we determine the lettericity of cycles and paths (the latter only to within an interval of length one) and show that for large n there are n-vertex graphs whose lettericity exceeds 0.707 n. In Section 6 we show that the class of k-letter graphs is well-quasi-ordered by ≤_{i} and has a finite set of minimal forbidden induced subgraphs. As a consequence, for any fixed k the class of k-letter graphs can be recognized in polynomial time.

2 Definitions and notation

Our graphs are undirected and simple. We write x ∼_{G} y if x and y are adjacent vertices of G. As a set of pairs, the adjacency relation in V (G) is denoted by Adj_{G}. The complement of a graph G is denoted by \overline{G}. If A is a set of graphs we write \overline{A} for the set \{\overline{G}; G ∈ A\}. The disjoint union of G_{1} and G_{2} is denoted by G_{1} + G_{2}, and the disjoint union of n copies of G is denoted by nG. As usual, K_{n} denotes the complete graph on n vertices, K_{p,q} the complete bipartite graph on p + q vertices, P_{n} the path on n vertices, and C_{n} the cycle of length n. The vertex set of P_{n} is {1, 2, …, n}, with i ∼_{P_{n}} (i + 1) for i = 1, 2, …, n − 1. The vertex set of C_{n} is {0, 1, …, n − 1}, with i ∼_{C_{n}} (i + 1) mod n for i = 0, 1, …, n − 1. If A is a set of graphs closed under taking induced subgraphs we denote by Obs(A) the set of obstructions or minimal forbidden induced subgraphs for A (i.e., the minimal elements of the complement of A quasi-ordered by the induced subgraph relation). The isomorphism relation among graphs is denoted by ≅. By z(G) we denote the cochromatic number of G, which is the minimum cardinality of a partition of V (G) into subsets that are either a clique or an independent set.

Let Σ be a finite alphabet and Σ^{∗} the set of all words over Σ (i.e., the free monoid generated by Σ under concatenation). For a word w = s_{1}s_{2} … s_{n} ∈ Σ^{∗} where s_{i} ∈ Σ, let w^{R} = s_{n}s_{n−1} … s_{1} denote its reverse. If A is a set of words we write A^{R} for {w^{R}; w ∈ A}.

Let P ⊆ Σ^{2} be a fixed set of ordered pairs of symbols from Σ. To each word w = w_{1}w_{2} … w_{n} where w_{i} ∈ Σ we assign its letter graph G(P, w) in the following way:

V (G(P, w)) = {1, 2, …, n},
E(G(P, w)) = {{i, j}; w_{min(i,j)}w_{max(i,j)} ∈ P}.

The vertices of G(P, w) are naturally labelled with the symbols of w.

Example 1 Take Σ = {a, b, c}, P = {ac, ba, cb, bb}, and w = abcabc. The corresponding letter graph G(P, w) is shown in Fig. 1 where vertex i is labelled with s_{i}. In this case, G(P, w) is the 6-cycle C_{6}.

[figure: a; b; c; a; b; c]

Figure 1: C_{6} as a 3-letter graph (P = {ac, ba, cb, bb}).

Denote G_{Σ}(P) = {G(P, w); w ∈ Σ^{∗}},

G_{k} = ⋃_{|Σ|=k, P⊆Σ^{2}} G_{Σ}(P),

l(G) = min{k; G ∈ G_{k}}.

Thus G_{k} is the set of all graphs that are letter graphs over some alphabet of size k, and l(G) is the least alphabet size that suffices to represent G as a letter graph. The graphs from G_{k} will be called k-letter graphs, and l(G) the lettericity of G. Example 1 shows that l(C_{6}) ≤ 3.

3 Some properties of k-letter graphs

First we restate the definition of k-letter graphs in purely graph-theoretic terms.

Proposition 1 A graph G is a k-letter graph if and only if

1. there is a partition V_{1}, V_{2}, …, V_{p} of V (G) with p ≤ k such that each V_{i} is either a clique or an independent set in G, and

2. there is a linear ordering L of V (G) such that for each pair of indices 1 ≤ i, j ≤ p, i ≠ j, the intersection of Adj_{G} with V_{i} × V_{j} is one of

(a) L ∩ (V_{i} × V_{j}),
(b) L^{−1} ∩ (V_{i} × V_{j}),
(c) V_{i} × V_{j}, or
(d) ∅.

Proof: If G is a k-letter graph then G = G(P, w) for some P ⊆ Σ^{2} and w ∈ Σ^{∗} where |Σ| = k. Let a_{1}, a_{2}, …, a_{p} be the different symbols from Σ that actually appear in w. Define

V_{i} = {v ∈ V (G); w_{v} = a_{i}} (1 ≤ i ≤ p).

If a_{i}a_{i} ∈ P then V_{i} is a clique, otherwise it is an independent set. Let L be the order induced on the vertices of V (G) by the linear ordering of their labels in w, and 1 ≤ i ≠ j ≤ p. We distinguish four cases:

(a) a_{i}a_{j} ∈ P, a_{j}a_{i} ∉ P: If x ∈ V_{i} and y ∈ V_{j} then x ∼ y if and only if xLy, so Adj_{G} ∩ (V_{i} × V_{j}) = L ∩ (V_{i} × V_{j}).

(b) a_{i}a_{j} ∉ P, a_{j}a_{i} ∈ P: If x ∈ V_{i} and y ∈ V_{j} then x ∼ y if and only if yLx, so Adj_{G} ∩ (V_{i} × V_{j}) = L^{−1} ∩ (V_{i} × V_{j}).

(c) a_{i}a_{j} ∈ P, a_{j}a_{i} ∈ P: In this case x ∼ y for all x ∈ V_{i} and y ∈ V_{j}, so Adj_{G} ∩ (V_{i} × V_{j}) = V_{i} × V_{j}.

(d) a_{i}a_{j} ∉ P, a_{j}a_{i} ∉ P: In this case x ≁ y for all x ∈ V_{i} and y ∈ V_{j}, so Adj_{G} ∩(V_{i} ×V_{j}) = ∅.

Conversely, let G be a graph on n vertices which satisfies conditions 1 and 2. Take Σ = {a_{1}, a_{2}, …, a_{p}} and

P = {a_{i}a_{i}; V_{i} clique}
⋃ {a_{i}a_{j}; i ≠ j, Adj_{G} ∩ (V_{i} × V_{j}) = L ∩ (V_{i} × V_{j})}
⋃ {a_{j}a_{i}; i ≠ j, Adj_{G} ∩ (V_{i} × V_{j}) = L^{−1} ∩ (V_{i} × V_{j})}
⋃ {a_{i}a_{j}, a_{j}a_{i}; i ≠ j, Adj_{G} ∩ (V_{i} × V_{j}) = V_{i} × V_{j}}.

Number the vertices of G so that v_{1} L v_{2} L … L v_{n}, and define w = s(v_{1})s(v_{2}) … s(v_{n}) where s(x) = a_{i} if x ∈ V_{i}. We claim that the mapping v_{i} ↦ i is an isomorphism from G to H = G(P, w).

Let x = v_{l} ∈ V_{i} and y = v_{m} ∈ V_{j}. First assume that x ∼_{G} y. If i = j then V_{i} = V_{j} must be a clique in G, so a_{i}a_{j} = a_{i}a_{i} ∈ P and hence l ∼_{H} m. If i ≠ j we distinguish four cases corresponding to those in condition 2:

(a) Adj_{G} ∩ (V_{i} × V_{j}) = L ∩ (V_{i} × V_{j}): In this case a_{i}a_{j} ∈ P. As x L y, we have l < m and hence l ∼_{H} m.

(b) Adj_{G} ∩ (V_{i} × V_{j}) = L^{−1} ∩ (V_{i} × V_{j}): In this case a_{j}a_{i} ∈ P. As x L^{−1} y, we have l > m and hence l ∼_{H} m.

(c) Adj_{G} ∩ (V_{i} × V_{j}) = V_{i} × V_{j}: In this case a_{i}a_{j} ∈ P and a_{j}a_{i} ∈ P, hence l ∼_{H} m.

(d) Adj_{G} ∩ (V_{i} × V_{j}) = ∅: This case is impossible because by assumption, (x, y) ∈ Adj_{G} ∩ (V_{i} × V_{j}).

Now assume that l ∼_{H} m and, w.l.o.g., that l < m. Then a_{i}a_{j} ∈ P and x L y. If i = j then V_{i} = V_{j} is a clique in G, so x ∼_{G} y. If i ≠ j we distinguish three cases corresponding to those in the definition of P:

(a) Adj_{G} ∩ (V_{i} × V_{j}) = L ∩ (V_{i} × V_{j}): As x L y, it follows that x ∼_{G} y.

(b) Adj_{G} ∩ (V_{j} × V_{i}) = L^{−1} ∩ (V_{j} × V_{i}): As y L^{−1} x, it follows that x ∼_{G} y.

(c) Adj_{G} ∩ (V_{i} × V_{j}) = V_{i} × V_{j}: In this case x ∼_{G} y for all x ∈ V_{i} and y ∈ V_{j}. □

Corollary 1 Let G be a k-letter graph. Then V (G) can be partitioned into p ≤ k sets V_{1}, V_{2}, …, V_{p} each of which is either a clique or an independent set in G, such that for each pair of indices 1 ≤ i, j ≤ p, i ≠ j, the family of neighborhoods N_{j}(x) = {y ∈ V_{j}; x ∼_{G} y} of all x ∈ V_{i} forms a chain of subsets of V_{j}.

Proof: Let L be the linear order on V (G) described in Proposition 1. Pick x, y ∈ V_{i} such that x L y. If Adj_{G} ∩ (V_{i} × V_{j}) = L ∩ (V_{i} × V_{j}) and y ∼_{G} z ∈ V_{j} then y L z, so x L z and x ∼_{G} z, hence N_{j}(y) ⊆ N_{j}(x). If Adj_{G} ∩ (V_{i} × V_{j}) = L^{−1} ∩ (V_{i} × V_{j}) and x ∼_{G} z ∈ V_{j} then z L x, so z L y and y ∼_{G} z, hence N_{j}(x) ⊆ N_{j}(y). If Adj_{G} ∩ (V_{i} × V_{j}) = V_{i} × V_{j} then N_{j}(x) = N_{j}(y) = V_{j}. If Adj_{G} ∩ (V_{i} × V_{j}) = ∅ then N_{j}(x) = N_{j}(y) = ∅. In all four cases, one of N_{j}(x), N_{j}(y) is a subset of the other. □

Next we list some simple observations without proof. Let f : Σ_{1} → Σ_{2} be a bijection, extended to Σ_{1}^{∗} as a homomorphism.

Proposition 2 (i) G(f(P), f(w)) = G(P, w).

(ii) G(P^{R}, w^{R}) = G(P, w).

(iii) G(Σ^{2} \ P, w) = \overline{G(P, w)}.

Corollary 2 (i) G_{Σ_{2}}(f(P)) = G_{Σ_{1}}(P).

(ii) G_{Σ}(P^{R}) = G_{Σ}(P).

(iii) G_{Σ}(Σ^{2} \ P) = \overline{G_{Σ}(P)}.

Proposition 3 (i) If n = |V (G)| ≥ 2 then z(G) ≤ l(G) ≤ n − 1.

(ii) l(G) = 1 if and only if G ≅ K_{n} or G ≅ \overline{K_{n}}.

(iii) l(\overline{G}) = l(G).

If z is a (not necessarily contiguous) subword of w then G(P, z) is an induced subgraph of G(P, w). Hence the set G_{Σ}(P) is closed under taking induced subgraphs, and therefore has a characterization with forbidden induced subgraphs. The same is true for G_{k}. Thus lettericity is a monotone parameter w.r.t. the induced subgraph relation.

4 2-letter graphs

By Proposition 1, 2-letter graphs are bipartite, split, or cobipartite graphs. In this section we characterize cobipartite 2-letter graphs as unbounded-interval graphs, and split 2-letter graphs as threshold graphs. We also show how our representation helps enumerate the pairwise nonisomorphic n-vertex graphs in these classes. For a fixed set of pairs P write w_{1} ∼ w_{2} whenever G(P, w_{1}) ≅ G(P, w_{2}). Clearly, this is an equivalence relation in the set Σ^{n} of words of length n over Σ.

4.1 Unbounded-interval graphs

An unbounded-interval graph is the intersection graph of a family of intervals of infinite length on the real line. We denote the set of unbounded-interval graphs by U. Unbounded-interval graphs are studied in [10]. Complements of unbounded-interval graphs are studied in [4].

Example 2 Let I_{1} = (−∞, 0], I_{2} = [1, ∞), I_{3} = (−∞, 2], and I_{4} = [3, ∞) (see Fig. 2). The intersection graph of these four intervals is the path P_{4}, which is therefore an unboundedinterval graph.

[figure: I_{1}; I_{3}; I_{2}; I_{4}; 0; 2; 1; 3; I_{1}; I_{2}; I_{3}; I_{4}]

Figure 2: A family of unbounded intervals whose intersection graph is P_{4}.

The following characterization of unbounded-interval graphs can be found in [10]:

Theorem 1 For a graph G, the following assertions are equivalent:

(i) G ∈ U,

(ii) G is triangulated and \overline{G} is bipartite,

(iii) G has no induced subgraphs isomorphic to \overline{K_{3}}, C_{4}, or C_{5},

(iv) G ∈ G_{Σ}(P) where Σ = {L, R} and P = {LL, RR, RL}.

In (iv), vertices corresponding to intervals unbounded on the left (resp. right) are labelled a (resp. b). Fig. 2 shows the example G(P, LRLR) ≅ P_{4}.

Let f(w) = w^{R}|_{L↔R} be the word obtained by reversing w and swapping L’s and R’s. Let → be a rewrite relation defined by

w → f(w),
wL ↔ Rw.

It turns out that the reflexive-transitive closure of → in Σ^{n} coincides with the equivalence relation ∼ defined at the beginning of the section. This fact is used in [10] to show that the number of nonisomorphic n-vertex unbounded-interval graphs is 2^{n−2} + 2^{⌊n/2⌋−1}.

4.2 Threshold graphs

A graph G is called threshold if there is a labelling f of its vertices by nonnegative integers, and an integer threshold t such that a set X ⊆ V (G) is independent if and only if ∑_{v∈X} f(v) ≤ t. We denote the set of threshold graphs by T .

Threshold graphs were introduced by Chvátal and Hammer in [1] where the following theorem is proved (see also [2], [7]):

Theorem 2 For a graph G, the following assertions are equivalent:

(i) G ∈ T ,

(ii) G has no induced subgraphs isomorphic to \overline{C_{4}}, C_{4}, or P_{4},

(iii) if δ_{1} < δ_{2} < ⋯ < δ_{m} are the degrees of the nonisolated vertices of G, δ_{0} = 0, D_{i} is the set of all vertices of degree δ_{i}, x ∈ D_{i}, y ∈ D_{j}, and x ≠ y, then x is adjacent to y iff i + j > m.

Here we characterize threshold graphs as 2-letter graphs.

Theorem 3 T = G_{Σ}(P) where Σ = {C, S} and P = {CC, CS}.

Proof: Consider a word w ∈ Σ^{∗}, partitioned into blocks of successive C’s and S’s:

w = S^{p_{0}}C^{q_{0}}S^{p_{1}}C^{q_{1}} ⋯ S^{p_{k}}C^{q_{k}},

where p_{0}, q_{k} ≥ 0, p_{1}, …, p_{k}, q_{0}, …, q_{k−1} > 0. Let G = G(P, w). By changing the last letter of w if necessary, we can assume that the last nonempty block of w has length at least two. As both C and S have identical sets of left neighbors in P, such change does not affect G. Let D_{i} be the set of vertices of G corresponding to the i-th block of S’s in w, and D_{m−i} the set of vertices corresponding to the i-th block of C’s where m is the total number of nonempty blocks in the subword C^{q_{0}}S^{p_{1}}C^{q_{1}} ⋯ S^{p_{k}}C^{q_{k}}. It is straightforward to verify that:

1) vertices within D_{i} have identical degree, say δ_{i}, 2) 0 = δ_{0} < δ_{1} < ⋯ < δ_{m}, and 3) distinct vertices x ∈ D_{i} and y ∈ D_{j} are adjacent iff i + j > m. By Theorem 2(iii), G is a threshold graph.

Conversely, let G be a threshold graph. Partition V (G) into D_{0}, D_{1}, …, D_{m} as described in Theorem 2(iii), and let d_{i} = |D_{i}|, x = S if m is even, x = C if m is odd, and w = S^{d_{0}}C^{d_{m}}S^{d_{1}}C^{d_{m−1}} ⋯ x^{d_{⌈m/2⌉}}. It is straightforward to verify that G ≅ G(P, w). □

Let → be a rewrite relation defined by

wC ↔ wS.

It is easy to see that the reflexive-transitive closure of → in Σ^{n} coincides with the equivalence relation ∼ defined at the beginning of the section. From this it follows immediately that the number of nonisomorphic n-vertex threshold graphs is 2^{n−1}.

4.3 An overview of 2-letter graphs

Theorem 4 G_{2} = T ∪ U ∪ \overline{U}.

Proof: Table 1 gives an overview of the 16 possible classes of 2-letter graphs over Σ = \{a, b\}, their minimal forbidden induced subgraphs, and their census. As K_{p}, \overline{K_{p}}, K_{p} + qK_{1}, \overline{K_{p} + qK_{1}} ∈ T , K_{p} + K_{q} ∈ U, and K_{p,q} ∈ \overline{U}, the theorem follows. □

elements  elements of number of pairwise nonisomorphic
of P  G_{Σ}(P)  Obs(G_{Σ}(P))  n-vertex graphs in G_{Σ}(P)
−  \{\overline{K_{p}}\}  K_{2}  1
aa  \{K_{p} + qK_{1}\}  P_{3}, \overline{C_{4}}  n
bb  \{K_{p} + qK_{1}\}  P_{3}, \overline{C_{4}}  n
ab  \overline{U}  K_{3}, \overline{C_{4}}, C_{5}  2^{n−2} + 2^{⌊n/2⌋−1}
ba  \overline{U}  K_{3}, \overline{C_{4}}, C_{5}  2^{n−2} + 2^{⌊n/2⌋−1}
aa, bb  \{K_{p} + K_{q}\}  P_{3}, \overline{K_{3}}  ⌊n/2⌋ + 1
aa, ab  T  \overline{C_{4}}, P_{4}, C_{4}  2^{n−1}
aa, ba  T  \overline{C_{4}}, P_{4}, C_{4}  2^{n−1}
bb, ab  T  \overline{C_{4}}, P_{4}, C_{4}  2^{n−1}
bb, ba  T  \overline{C_{4}}, P_{4}, C_{4}  2^{n−1}
ab, ba  \{K_{p,q}\}  \overline{P_{3}}, K_{3}  ⌊n/2⌋ + 1
aa, bb, ab  U  \overline{K_{3}}, C_{4}, C_{5}  2^{n−2} + 2^{⌊n/2⌋−1}
aa, bb, ba  U  \overline{K_{3}}, C_{4}, C_{5}  2^{n−2} + 2^{⌊n/2⌋−1}
aa, ab, ba  \overline{K_{p} + qK_{1}}  \overline{P_{3}}, C_{4}  n
bb, ab, ba  \overline{K_{p} + qK_{1}}  \overline{P_{3}}, C_{4}  n
aa, bb, ab, ba  \{K_{p}\}  \overline{K_{2}}  1

Table 1: 2-letter graphs (p and q denote nonnegative integers).

Corollary 3 All graphs on four or fewer vertices are 2-letter graphs.

Proof: According to Theorem 2(ii), all graphs on four or fewer vertices except \overline{C_{4}}, P_{4}, and C_{4} are threshold graphs. As \overline{C_{4}} ∈ U, C_{4} ∈ \overline{U}, and P_{4} ∈ U ∩ \overline{U}, the claim follows from Theorem 4. □

Corollary 4 Obs(G_{2}) is finite.

Proof: From Theorem 4 and Table 1 it follows that the graphs not in G_{2} have at least one induced subgraph in each of the sets \{\overline{C_{4}}, P_{4}, C_{4}\}, \{\overline{K_{3}}, C_{4}, C_{5}\}, and \{K_{3}, \overline{C_{4}}, C_{5}\}. Checking all 27 combinations and discarding redundant ones we see that such graphs contain at least one of the following seven sets of induced subgraphs: \{\overline{C_{4}}, C_{4}\}, \{\overline{K_{3}}, \overline{C_{4}}\}, \{\overline{C_{4}}, C_{5}\}, \{\overline{K_{3}}, K_{3}, P_{4}\}, \{P_{4}, C_{5}\}, \{K_{3}, C_{4}\}, \{C_{4}, C_{5}\}. Thus a minimal forbidden induced subgraph for G_{2} can have at most 3 + 3 + 4 = 10 vertices. □

Corollary 5 2-letter graphs can be recognized in polynomial time.

Proof: This follows from Theorem 4 because each of the classes T , U, \overline{U} has a polynomialtime recognition algorithm. □

5 Lettericity of some n-vertex graphs

In this section we consider the lettericity of cycles, paths, and perfect matchings. By a counting argument we show that for large n there are n-vertex graphs whose lettericity exceeds 0.707 n.

5.1 Cycles

Call an independent set S in C_{n} tight if S = {k, (k + 2) mod n, …, (k + 2m) mod n} for some k ∈ {0, 1, …, n − 1} and m ≥ 0.

Lemma 1 Let G(P, w) ≅ C_{n}. If a ∈ Σ gives rise to an independent set S of size three or more in G(P, w) then:

(i) S is tight,

(ii) |S| = 3,

(iii) the labels of the two vertices of G(P, w) which have both neighbors in S are distinct.

Proof: (i) Let R be a maximal run of consecutive vertices of C_{n} which are not in S. If R has two or more vertices then the labels of the two vertices of S adjacent to one of the endpoints of R must be the leftmost and the rightmost a’s in w. Hence there is at most one such run, meaning that S is tight.

(ii) If S contains more than three vertices, it is tight by (i). W.l.g. assume that 0, 2, 4, 6 ∈ S. Then in w, the label of 1 (which is adjacent to 0 and 2, but not adjacent to 4 or 6) must be between the labels of 0, 2 and 4, 6, while the label of 3 must be between the labels of 2, 4 and 0, 6. As this is impossible, |S| = 3.

(iii) By (i) and (ii), S is tight and has three vertices. W.l.g. assume that S = {0, 2, 4}. If the vertices 1 and 3 are labelled the same, say b, these five vertices correspond to a subword ababa of w where the left b is the label of 3 and forces ba ∈ P, while the right b is the label of 1 and forces ab ∈ P. But then 1 and 3 would have degree three or more. It follows that vertices 1 and 3 must be labelled differently. □

Theorem 5 Let n ≥ 4. Then l(C_{n}) = ⌊\frac{n+4}{3}⌋.

Proof: First we prove that at least ⌊\frac{n+4}{3}⌋ letters are needed to obtain C_{n}. Let C_{n} ≅ G(P, w) where w contains m different letters. As n ≥ 4, the largest clique in C_{n} is of size 2. From Lemma 1(ii) it follows that each letter appears at most three times in w. Therefore n ≤ 3m and m ≥ ⌈n/3⌉. If n = 3k + 1 then ⌊\frac{n+4}{3}⌋ = k + 1 = ⌈n/3⌉, so the assertion is proved. If n = 3k or n = 3k − 1 then ⌊\frac{n+4}{3}⌋ = k + 1 = ⌈n/3⌉ + 1. It remains to show that in the latter two cases k = ⌈n/3⌉ letters do not suffice.

a) n = 3k

Assume that w is a word consisting of k different letters whose letter graph is C_{3k}. By Lemma 1(ii), each letter gives rise to an independent set of size three. By Lemma 1(i) and (iii), the vertices of C_{3k} must be (cyclically) labelled a_{1}^{1}a_{k}^{3}a_{1}^{2}a_{2}^{1}a_{1}^{3}a_{2}^{2}a_{3}^{1}a_{2}^{3}a_{3}^{2} … a_{k}^{2}a_{1}^{1} where superscripts distinguish the three occurrences of each letter. It remains to see how these symbols could be arranged linearly in w.

As a_{k}^{3} is adjacent to a_{1}^{1} and a_{1}^{2}, while a_{2}^{1} is adjacent to a_{1}^{2} and a_{1}^{3}, it follows that a_{1}^{2} must be between a_{1}^{1} and a_{1}^{3} in w. W.l.g. assume that the arrangement of these symbols in w is a_{1}^{1}a_{1}^{2}a_{1}^{3}. By induction on i it can be shown that a_{i}^{1} precedes a_{i}^{2} which precedes a_{i}^{3} in w, and also that a_{i−1}^{1} precedes a_{i}^{1}, for i = 2, 3, …, k. Hence a_{1}^{1} precedes all three occurrences of a_{k} in w. However, being adjacent to exactly two of the corresponding vertices this is impossible.

b) n = 3k − 1

As before, assume that w is a word consisting of k different letters whose letter graph is C_{3k−1}. This is only possible if k − 1 of the letters give rise to an independent set of size three, and the remaining letter, say a_{1}, gives rise to either a clique or an independent set of size two. In case of a clique, an independent set bordering on it must have the intervening two vertices labelled the same, contrary to Lemma 1(iii). So a_{1} gives rise to an independent set of size two.

By Lemma 1(i) and (iii), the only possible way to label (cyclically) the vertices of C_{3k−1} is a_{1}^{1}a_{k}^{3}a_{2}^{1}a_{1}^{2}a_{2}^{2}a_{3}^{1}a_{2}^{3}a_{3}^{2} … a_{k}^{2}a_{1}^{1} where superscripts distinguish different occurrences of each letter. It remains to see how these symbols could be arranged linearly in w. Similarly as in the case a) we can establish that a_{i}^{1} precedes a_{i}^{2} which precedes a_{i}^{3} in w, for i = 2, 3, …, k, and also that a_{i−1}^{1} precedes a_{i}^{1}, for i = 3, 4, …, k. Hence a_{2}^{1} precedes all three occurrences of a_{k} in w. However, being adjacent to exactly one of the corresponding vertices this is impossible.

It remains to construct C_{n} using no more than ⌊\frac{n+4}{3}⌋ letters. We distinguish three cases w.r.t. n mod 3. In all three cases, the alphabet is Σ = \{a_{0}, a_{1}, …, a_{k}\} where k = ⌊\frac{n+1}{3}⌋. Let P_{c} = {a_{i}a_{i−1 (mod k+1)} ; 0 ≤ i ≤ k}.

a) n = 3k + 1 Take P = P_{c} and w = a_{0}^{1}a_{1}^{1} ⋯ a_{k}^{1}a_{0}^{2}a_{1}^{2} ⋯ a_{k}^{2}a_{0}^{3}a_{1}^{3} ⋯ a_{k−2}^{3} where superscripts are added for easier reference. Write t_{i} = a_{i}^{1}a_{i−1}^{2}a_{i−2}^{3}. Then it is easy to check that G(P, w) is the cycle t_{k}t_{k−1} ⋯ t_{2}a_{1}^{1}a_{0}^{2}a_{k}^{2}a_{0}^{1}a_{k}^{1} of length 3k + 1.

b) n = 3k Take P = P_{c} ∪ {a_{k−1}a_{k−1}} and w = a_{0}^{1}a_{1}^{1} ⋯ a_{k}^{1}a_{0}^{2}a_{1}^{2} ⋯ a_{k}^{2}a_{0}^{3}a_{1}^{3} ⋯ a_{k−3}^{3}. As before, write t_{i} = a_{i}^{1}a_{i−1}^{2}a_{i−2}^{3}. Then it is easy to check that G(P, w) is the cycle t_{k−1}t_{k−2} ⋯ t_{2}a_{1}^{1}a_{0}^{2}a_{k}^{2}a_{0}^{1}a_{k}^{1}a_{k−1}^{2}a_{k−1}^{1} of length 3k. For n = 6 this construction is shown in Fig. 1 (with a_{0} = a, a_{1} = b, a_{2} = c).

c) n = 3k − 1 If k = 2 take P = {a_{0}a_{2}, a_{1}a_{0}, a_{2}a_{1}, a_{1}a_{1}, a_{0}a_{0}} and w = a_{0}a_{1}a_{2}a_{0}a_{1}. Then G(P, w) ≅ C_{5}. If k ≥ 3 let P = P_{c} ∪ {a_{k−1}a_{k−1}, a_{k−2}a_{k−2}} and w = a_{0}^{1}a_{1}^{1} ⋯ a_{k}^{1}a_{0}^{2}a_{1}^{2} ⋯ a_{k}^{2}a_{0}^{3}a_{1}^{3} ⋯ a_{k−4}^{3}. Write again t_{i} = a_{i}^{1}a_{i−1}^{2}a_{i−2}^{3}. Then it is easy to check that G(P, w) is the cycle t_{k−2}t_{k−3} ⋯ t_{2}a_{1}^{1}a_{0}^{2}a_{k}^{2}a_{0}^{1}a_{k}^{1}a_{k−1}^{2}a_{k−1}^{1}a_{k−2}^{2}a_{k−2}^{1} of length 3k − 1. □

5.2 Paths

Lemma 2 Let G(P, w) ≅ P_{n}. If a ∈ Σ gives rise to an independent set S of size three or more in G(P, w) then S is of one of the following types:

(a) {1, 3, n − 2, n},

(b) {1, 3, i}, where 6 ≤ i ≤ n,

(c) {i, n − 2, n}, where 1 ≤ i ≤ n − 5,

(d) {i, i + 2, i + 4}, where 2 ≤ i ≤ n − 5.

Proof: Similar to that of Lemma 1. □

Theorem 6 ⌊\frac{n+1}{3}⌋ ≤ l(P_{n}) ≤ ⌊\frac{n+4}{3}⌋.

Proof: For the upper bound, we show how to construct P_{n} using no more than ⌊\frac{n+4}{3}⌋ letters. We distinguish two cases w.r.t. n mod 3.

a) n = 3k + 1 Let Σ = {a_{0}, a_{1}, …, a_{k}}, P = {a_{i}a_{i−1 (mod k+1)} ; 0 ≤ i ≤ k − 1}, and w = a_{0}^{1}a_{1}^{1} ⋯ a_{k}^{1}a_{0}^{2}a_{1}^{2} ⋯ a_{k}^{2}a_{0}^{3}a_{1}^{3} ⋯ a_{k−2}^{3} where superscripts are added for easier reference. Write t_{i} = a_{i}^{2}a_{i−1}^{3}a_{i}^{1}. Then it is easy to check that G(P, w) is the path t_{k−1}t_{k−2} ⋯ t_{1}a_{0}^{2}a_{k}^{2}a_{0}^{1}a_{k}^{1} of length 3k + 1.

b) n = 3k or n = 3k − 1 By Theorem 5, C_{n+1} can be constructed using k + 1 letters. The same then goes for P_{n} as it is an induced subgraph of C_{n+1}.

For the lower bound, let P_{n} ≅ G(P, w) where w contains m different letters. Lemma 2 implies that at most one letter can appear four times in w, while the rest can appear three times at most. Therefore n ≤ 4 + 3(m − 1), so m ≥ ⌈(n − 1)/3⌉ = ⌊(n + 1)/3⌋. □

Conjecture: If n ≥ 3 then l(P_{n}) = ⌊\frac{n+4}{3}⌋.

5.3 Maximum lettericity of n-vertex graphs

Let l(n) denote the maximum lettericity of an n-vertex graph. Clearly, l(1) = l(2) = 1 and l(3) = l(4) = 2. As l(G) ≥ z(G), the maximum cochromatic number of an n-vertex graph (which is known to be of order n/ log n [8]) constitutes a lower bound for l(n). But this is a poor bound: we have seen that the lettericity of paths and cycles on n vertices is about n/3 which is much larger than n/ log n when n is large. It is also easy to see that l(nK_{2}) = n and l(nK_{2} + K_{1}) = n + 1, so, in fact, l(n) ≥ n/2. By a counting argument we now improve this bound to l(n) > 0.707 n, provided that n is large enough.

Theorem 7 For each α < \frac{\sqrt{2}}{2} there is an N such that for all n > N there are n-vertex graphs G with l(G) > α n.

Proof: Assume that l(G) ≤ α n for all graphs G on n vertices. Write k = ⌊α n⌋; then, by our assumption, all graphs on n vertices are k-letter graphs. There are 2^{\binom{n}{2}} labelled graphs on n vertices. Over a k-letter alphabet, there are k^{2} pairs of letters, 2^{k^{2}} sets of pairs of letters, k^{n} words of length n, and at most n! possible labellings of a graph on n vertices, hence there are no more than n! k^{n}2^{k^{2}} labelled k-letter graphs on n vertices. Therefore

2^{\binom{n}{2}} ≤ n! k^{n}2^{k^{2}} ≤ n^{n}(α n)^{n}2^{(α n)^{2}}.

Taking base 2 logarithms we have

(\frac{1}{2} − α^{2}) n^{2} ≤ 2 n lg n + (\frac{1}{2} + lg α) n.

Since 1/2 > α^{2} this is impossible when n is large. □

As for a simple upper bound, Proposition 3(i) implies that l(n) ≤ n − 1 when n ≥ 2. It is also not difficult to see that l(n) ≤ n − 2 when n ≥ 4.

6 k-letter graphs and well-quasi-order

By deleting a vertex the lettericity of a graph can decrease by more than one: for example, l(C_{5} + K_{1}) = 4 but l(P_{4} + K_{1}) = 2. We need an upper bound on the extent of this decrease.

Lemma 3 l(G) ≤ 2 l(G − v) + 1 for all v ∈ V (G).

Proof: Let l(G − v) = k. Then G − v = G(P, w) for some P ⊆ Σ^{2} and w ∈ Σ^{∗} where Σ = {a_{1}, …, a_{k}}. Let a_{i_{1}}, …, a_{i_{r}} be the labels of the neighbors of v in w. Take Σ′ = Σ ∪ {a′_{1}, …, a′_{k}, b} where a′_{1}, …, a′_{k}, b are new symbols, and P′ = P ∪ {a′_{j}a′_{l}, a′_{j}a_{l}, a_{j}a′_{l}; a_{j}a_{l} ∈ P} ∪ {a′_{i_{j}}b; 1 ≤ j ≤ r}. Denote by w′ the word obtained from w by replacing the labels a_{i} of the neighbors of v by a′_{i}. Then G = G(P′, w′b). Hence l(G) ≤ |Σ′| = 2k + 1 as claimed. □

Theorem 8 The class G_{k} of k-letter graphs is well-quasi-ordered by the induced subgraph relation.

Proof: Fix an alphabet Σ of cardinality k and a set of pairs P ⊆ Σ^{2}. By Higman’s Lemma [9, Thm. 4.4], Σ^{∗} is well-quasi-ordered by the (not necessarily contiguous) subword relation. Clearly, z is a subword of w if and only if G(P, z) is an induced subgraph of G(P, w), hence G_{Σ}(P) is well-quasi-ordered by the induced subgraph relation. As G_{k} is a union of finitely many sets of the form G_{Σ}(P) (one for each of the 2^{k^{2}} possible P’s) the conclusion follows. □

Theorem 9 The sets of obstructions Obs(G_{Σ}(P)) and Obs(G_{k}) are finite.

Proof: If G ∈ Obs(G_{Σ}(P)) then G − v ∈ G_{Σ}(P) for each v ∈ V (G). Let k = |Σ|. By Lemma 3, l(G) ≤ 2k + 1, hence Obs(G_{Σ}(P)) ⊆ G_{2k+1}. As Obs(G_{Σ}(P)) is an antichain, Theorem 8 implies that it is finite.

Finiteness of Obs(G_{k}) is proved in the same way. □

Corollary 6 The graphs from G_{Σ}(P) and G_{k} are recognizable in polynomial time.

Proof: The relation H ≤_{i} G is decidable in time O(n^{m}) where n = |V (G)| and m = |V (H)|. For fixed H this is polynomial in n. Thus by Theorem 9, checking that H ≰_{i} G for all H ∈ Obs(G_{Σ}(P)) (resp. H ∈ Obs(G_{k})) where G is given is a polynomial-time recognition algorithm for G_{Σ}(P) (resp. G_{k}). □

Note that the proof of Corollary 6 is nonconstructive as the specification of the algorithm given there is incomplete: the finite sets of obstructions for G_{Σ}(P) and G_{k} that are used by the algorithm are, in general, unknown.

7 Conclusion

We conclude by listing some open problems.

Problem 1. Design efficient algorithms to recognize k-letter graphs for small fixed values of k.

Problem 2. What is the time complexity of finding the lettericity of a given graph?

Problem 3. Find the maximal possible lettericity of an n-vertex graph, and the corresponding extremal graphs.

Acknowledgements

The author is indebted to Bojan Mohar and Tomaž Pisanski for helping out with this paper (in particular, Tomaž suggested that k-letter graphs should be recognizable in polynomial time, and Bojan pointed out Theorem 7). He also wishes to thank the referees for their careful reading of the paper and valuable suggestions.

References

[1] V. Chvátal, P. Hammer: Set-packing and threshold graphs, Univ. Waterloo Res. Report, CORR 73-21.

[2] V. Chvátal, P. Hammer: Aggregation of inequalities in integer programming, in: Studies in integer programming (Proc. Workshop, Bonn, 1975), Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam 1977, 145–162.

[3] P. Damaschke: Induced subgraphs and well-quasi-ordering, J. Graph Theory 14 (1990) 427–435.

[4] G. Ding: Covering the edges with consecutive sets, J. Graph Theory 15 (1991) 559–562.

[5] G. Ding: Subgraphs and well-quasi-ordering, J. Graph Theory 16 (1992) 489–502.

[6] G. Ding: Stable sets versus independent sets, Discrete Math. 117 (1993) 73–87.

[7] M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.

[8] P. Erdös, J. Gimbel, D. Kratsch: Some extremal results in cochromatic and dichromatic theory, J. Graph Theory 15 (1991) 579–585.

[9] G. Higman: Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952) 326–336.

[10] S. Klavžar, M. Petkovšek: Intersection graphs of halflines and halfplanes, Discrete Math. 66 (1987) 133–137.

[11] J. B. Kruskal: Well-quasi-ordering, the tree theorem, and Vazsonyi’s conecture, Trans. Amer. Math. Soc. 95 (1960) 210–225.

[12] J. B. Kruskal: The theory of well-quasi-ordering: a frequently discovered concept, J. Comb. Theory (A) 13 (1972) 297–305.