Letter graphs and well-quasi-order by induced subgraphs.
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 the 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.
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 there are indices
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 embeddabil-
ity), 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
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
the class of graphs G such that for some R ' V (G) with jRj - r, the graph G \Gamma R
has matroidal number at most three [6],
ffl 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.
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 AdjG . The complement
of a graph G is denoted by G. If A is a set of graphs we write A for the set fG ; G 2 Ag.
The disjoint union of G 1 and G 2 is denoted by G 1 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
The vertex set of C n is f0;
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 \Sigma be a finite alphabet and \Sigma   the set of all words over \Sigma (i.e., the free monoid
generated by \Sigma under concatenation). For a word
its reverse. If A is a set of words we write A R for Ag.
Let P ' \Sigma 2 be a fixed set of ordered pairs of symbols from \Sigma. To each word
its letter graph G(P; w) in the following way:
The vertices of G(P; w) are naturally labelled with the symbols of w.
Example 1 Take 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 .
a b c a b c

Figure

1: C 6 as a 3-letter graph
Denote
G \Sigma (P);
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 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 -
the intersection of AdjG with V i \Theta V j is one of
(a)
(d) ;.
Proof: If G is a k-letter graph then
be the different symbols from \Sigma that actually appear in w. Define
If a i 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
distinguish four cases:
(a) a i a
only if xLy, so AdjG "
(b) a i a
(c) a i a In this case x - y for all x
(d) a i a
2 P: In this case x 6- y for all x
Conversely, let G be a graph on n vertices which satisfies conditions 1 and 2. Take
Number the vertices of G so that v 1
We claim that the mapping v i 7! i is an isomorphism from G to
First assume that x -G y. If must
be a clique in G, so a i a hence l -H m. If i 6= j we distinguish four cases
corresponding to those in condition 2:
In this case a i a j 2 P. As x L y, we have l ! m and
hence l -H m.
In this case a j a i 2 P. As x L \Gamma1 y, we have l ? m
and hence l -H m.
In this case a i a
This case is impossible because by assumption, (x; y) 2 AdjG "
Now assume that l -H m and, w.l.o.g., that l ! m. Then a i a y. If
then is a clique in G, so x -G y. If i 6= j we distinguish three cases corresponding
to those in the definition of P:
As x L y, it follows that x -G y.
As y L \Gamma1 x, it follows that x -G y.
In this case x -G y for all x
Corollary 1 Let G be a k-letter graph. Then V (G) can be partitioned into p - k sets
each of which is either a clique or an independent set in G, such that for each
pair of indices 1 - the family of neighborhoods N j
all a chain of subsets of V j .
Proof: Let L be the linear order on V (G) described in Proposition 1. Pick x; y
that x L y. If AdjG "
then z L x, so z L y and y -G z, hence N j (x) ' N j (y). If AdjG "
In all four cases, one
of N j (x), N j (y) is a subset of the other. 2
Next we list some simple observations without proof. be a bijection,
extended to \Sigma
1 as a homomorphism.
Proposition 2 (i) G(f(P);
(ii)
Corollary 2 (i) G \Sigma 2
(P).
Proposition 3 (i) If
only if 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 \Sigma (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
nonisomorphic n-vertex graphs in these classes. For a fixed set of pairs P write
this is an equivalence relation in the set
\Sigma n of words of length n over \Sigma.
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 Fig. 2). The
intersection graph of these four intervals is the path P 4 , which is therefore an unbounded-
interval graph.
I 1
I 3
I 2
I 423
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:
(ii) G is triangulated and G is bipartite,
(iii) G has no induced subgraphs isomorphic to K 3 , C 4 , or C 5 ,
RR;RLg.
In (iv), vertices corresponding to intervals unbounded on the left (resp. right) are labelled a
Fig. 2 shows the example
be the word obtained by reversing w and swapping L's and R's. Let
! be a rewrite relation defined by
It turns out that the reflexive-transitive closure of ! in \Sigma 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
4.2 Threshold graphs
A graph G is called threshold if there is a labelling f of its vertices by nonnegative inte-
gers, and an integer threshold t such that a set X ' V (G) is independent if and only if
t. We denote the set of threshold graphs by T .
Threshold graphs were introduced by Chv'atal 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:
(ii) G has no induced subgraphs isomorphic to C 4 , C 4 , or P 4 ,
are the degrees of the nonisolated vertices of G, is the
set of all vertices of degree y, then x is adjacent to y iff
Here we characterize threshold graphs as 2-letter graphs.
Theorem 3 CSg.
Proof: Consider a word w 2 \Sigma   , partitioned into blocks of successive C's and S's:
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 Dm\Gammai
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 . It is straightforward to verify that:
vertices within D i have identical degree, say distinct
vertices are adjacent iff 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 , . , Dm as described
in Theorem 2(iii), and let d
dm=2e . It is straightforward to verify that G
Let ! be a rewrite relation defined by
It is easy to see that the reflexive-transitive closure of ! in \Sigma 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
4.3 An overview of 2-letter graphs
Theorem 4 G
Proof:

Table

1 gives an overview of the possible classes of 2-letter graphs over
induced subgraphs, and their census. As K
the theorem follows. 2
elements elements of number of pairwise nonisomorphic
of P G \Sigma (P) Obs(G \Sigma (P)) n-vertex graphs in G \Sigma (P)
aa
ab U K 3

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 C
and C 4 are threshold graphs. As C 4 the claim follows from
Theorem 4. 2
Corollary 4
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 fC g. 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: fC
g. Thus a minimal forbidden induced subgraph for
G 2 can have at most 3 vertices. 2
Corollary 5 2-letter graphs can be recognized in polynomial time.
Proof: This follows from Theorem 4 because each of the classes T , U , U has a polynomial-time
recognition algorithm. 2
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 ng for
some
. If a 2 \Sigma gives rise to an independent set S of size three or
more in G(P; w) then:
(i) S is tight,
(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 2
S. Then in w, the label of 1 (which is adjacent to 0 and 2, but not adjacent to 4 or 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,
(iii) By (i) and (ii), S is tight and has three vertices. W.l.g. assume that 4g. 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 2 P, while the right b is the label
of 1 and forces ab 2 P. But then 1 and 3 would have degree three or more. It follows that
vertices 1 and 3 must be labelled differently. 2
Theorem 5 Let
Proof: First we prove that at least b n+4c letters are needed to obtain C n . Let C n
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
dn=3e, so the assertion is
proved. If It remains to show that
in the latter two cases letters do not suffice.
a)
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 3
k a 2
2 a 3
3 a 3
k 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 3
k is adjacent to a 1
1 and a 2
2 is adjacent to a 2
1 and a 3
1 , it follows that a 2
must
be between a 1
1 and a 3
1 in w. W.l.g. assume that the arrangement of these symbols in w is
a 1
1 a 3
1 . By induction on i it can be shown that a 1
precedes a 2
which precedes a 3
in w, and
also that a 1
precedes a 1
Hence a 1
1 precedes all three occurrences of a k in
However, being adjacent to exactly two of the corresponding vertices this is impossible.
As before, assume that w is a word consisting of k different letters whose letter graph is
C . This is only possible if of the letters give rise to an independent set of size
three, and the remaining letter, say a 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\Gamma1 is
a 1
1 a 3
k a 1
3 a 3
k 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 1
precedes a 2
which precedes a 3
i in w, for
that a 1
precedes a 1
Hence a 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 b n+4c letters. We distinguish three cases
w.r.t. n mod 3. In all three cases, the alphabet is
a)
k a 2
k a 3
k\Gamma2 where superscripts are added for
easier reference. Write t
i\Gamma2 . Then it is easy to check that G(P; w) is the cycle
k a 1
k of length 3k + 1.
k a 2
k a 3
k\Gamma3 . As be-
fore,
i\Gamma2 . Then it is easy to check that G(P; w) is the cycle
k a 1
k a 2
of length 3k. For construction is shown in
Fig. 1 (with a
c)
k a 2
k a 3
k\Gamma4 .
Write again t
i\Gamma2 . Then it is easy to check that G(P; w) is the cycle
k a 1
k a 2
k\Gamma2 a 1
k\Gamma2 of length 3k \Gamma 1. 2
5.2 Paths
. If a 2 \Sigma 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) f1; 3;
(b)
(c)
(d)
Proof: Similar to that of Lemma 1. 2
Theorem 6 b n+1c -
Proof: For the upper bound, we show how to construct P n using no more than b n+4c
letters. We distinguish two cases w.r.t. n mod 3.
a)
a 1
k a 2
k a 3
k\Gamma2 where superscripts are added for easier reference. Write
. Then it is easy to check that G(P; w) is the path t
k a 1
k of
length 3k + 1.
By Theorem 5, C n+1 can be constructed using 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
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
Conjecture: If n - 3 then
5.3 Maximum lettericity of n-vertex graphs
Let l(n) denote the maximum lettericity of an n-vertex graph. Clearly,
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
and 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 ff !
there is an N such that for all n ? N there are n-vertex
graphs G with l(G) ? ff n.
Proof: Assume that l(G) - ff n for all graphs G on n vertices. Write
our assumption, all graphs on n vertices are k-letter graphs. There are 2 ( n) 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!
labelled k-letter graphs on n vertices. Therefore
Taking base 2 logarithms we have
n:
this is impossible when n is large. 2
As for a simple upper bound, Proposition 3(i) implies that l(n) - 2. It
is also not difficult to see that l(n) -
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,
2. We need an upper bound on the extent of this decrease.
Proof: Let
g. Let a i 1
be the labels of the neighbors of v in w. Take \Sigma
are new symbols, and P
l ; a 0
l ; a j a l 2
rg. Denote by w 0 the word obtained from w by replacing the labels a i
of the neighbors of v by a 0
Theorem 8 The class G k of k-letter graphs is well-quasi-ordered by the induced subgraph
relation.
Proof: Fix an alphabet \Sigma of cardinality k and a set of pairs P ' \Sigma 2 . By Higman's Lemma
[9, Thm. 4.4], \Sigma   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 \Sigma (P) is well-quasi-ordered by the induced subgraph relation. As G k is a union of finitely
many sets of the form G \Sigma (P) (one for each of the 2 k 2
possible P's) the conclusion follows. 2
Theorem 9 The sets of obstructions Obs(G \Sigma (P)) and Obs(G k ) are finite.
As Obs(G \Sigma (P)) is an antichain,
Theorem 8 implies that it is finite.
Finiteness of Obs(G k ) is proved in the same way. 2
Corollary 6 The graphs from G \Sigma (P) and G k are recognizable in polynomial time.
Proof: The relation H - i G is decidable in time O(n m ) where
jV (H)j. For fixed H this is polynomial in n. Thus by Theorem 9, checking that H 6- i G for
is given is a polynomial-time recognition
algorithm for G \Sigma (P) (resp. G k ). 2
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 \Sigma (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-z Pisanski for helping out with this paper
(in particular, Toma-z 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.



--R


Aggregation of inequalities in integer programming
Induced subgraphs and well-quasi-ordering
Covering the edges with consecutive sets
Subgraphs and well-quasi-ordering
Stable sets versus independent sets
Algorithmic Graph Theory and Perfect Graphs
Some extremal results in cochromatic and dichromatic theory
Ordering by divisibility in abstract algebras
Intersection graphs of halflines and halfplanes

The theory of well-quasi-ordering: a frequently discovered concept
--TR
Intersection graphs of halflines and halfplanes
Induced subgraphs and well-quasi-ordering
Subgraphs and well-quasi-ordering
Stable sets versus independent sets
induced subgraph relation;lettericity;well-quasi-order