{'fraction_non_alphanumeric': 0.04488745561744682, 'fraction_numerical': 0.009739730935861102, 'mean_word_length': 3.492244659057653, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation

Recently, Daligault, Rao and Thomass\'e asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.


Introduction
Well-quasi-ordering is a highly desirable property and frequently discovered concept in mathematics and theoretical computer science [7,10]. One of the most remarkable recent results in this area is the proof of Wagner's conjecture stating that the set of all finite graphs is well-quasiordered by the minor relation [13]. However, the subgraph or induced subgraph relation is not a well-quasi-order. On the other hand, each of these relations may become a well-quasi-order under some additional restrictions. In this paper, we study well-quasi-orderability of graphs with hereditary properties.
A graph property (or a class of graphs) is a set of graphs closed under isomorphism. A property is hereditary if it is closed under taking induced subgraphs.
Recently, Daligault, Rao and Thomassé conjectured in [4] that every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. In the present paper, we verify this conjecture for subquadratic properties.
We say that a hereditary graph property X is subquadratic if there is a function f (n) = o(n 2 ) bounding the number of edges in all n-vertex graphs in X. The family of subquadratic properties contains many important classes such as graphs of bounded vertex degree, of bounded tree-width, all proper minor closed graph classes. In all these examples, the number of edges is bounded by a linear function in the number of vertices and all of the listed properties are rather small (see e.g. [11] for the number of graphs in proper minor closed graph classes). In the terminology of [1], they all are at most factorial. The family of subquadratic properties is much wider and contains classes with a superfactorial speed of growth, such as projective plane graphs (or more generally C 4 -free bipartite graphs), in which case the number of edges is Θ(n 3 2 ). In fact, as we show in Section 2, subquadratic properties have a nice structural characterization: these are precisely hereditary classes of graphs without large bicliques as subgraphs.
The main result of the paper is a theorem stating that a hereditary class which is wellquasi-ordered by the induced subgraph relation is of bounded tree-width if and only if it is subquadratic. This result verifies (and even strengthens) for subquadratic properties the conjecture of Daligault, Rao and Thomassé [4]. As a byproduct, we also show that for a finitely defined subquadratic property, it is a decidable (in fact, in polynomial time) task to test wellquasi-orderability by the induced subgraphs relation.
All preliminary information related to the topic of the paper can be found in Section 2, where we also prove a number of preparatory results.

Notations and preparatory results
We consider only simple undirected graphs without loops and multiple edges. An independent set in a graph is a set of vertices no two of which are adjacent, and a clique is a set of vertices every two of which are adjacent. As usual, by K n , P n and C n we denote the complete graph, the chordless path and the chordless cycle on n vertices, respectively, and K n,m is a complete bipartite graph with parts of size n and m. Sometimes we also refer to K n as a clique and to K n,m as a biclique. If n = m we say that K n,m is a biclique of order n.
Given a graph G and a subset U of its vertices, the operation of contraction of U into a single vertex u consists in deleting U , introducing u and connecting u to every vertex of G outside U that has a neighbour in U . If U consists of two adjacent vertices, this operation is called edge contraction.
Let H and G be two graphs. We say that • H is an induced subgraph of G if H can be obtained from G by vertex deletions, • H is a subgraph of G if H can be obtained from G by vertex deletions and edge deletions, • H is a minor of G if H can be obtained from G by vertex deletions, edge deletions and edge contractions.
Throughout the text, whenever we say that G contains H, we mean that H is subgraph of G, unless we explicitly say that H is an induced subgraph of G (or G contains H as an induced subgraph). If H is not an induced subgraph of G, we say that G is H-free.
By R = R(k, r, m), we denote the Ramsey number, i.e. the minimum R such that in every coloring of k-subsets of an R-set with r colors there is a monochromatic m-set, i.e. a set of m elements all of whose k-subsets have the same color.

Well-quasi-ordering and infinite antichains
A binary relation ≤ on a set X is a quasi-order if it is reflexive and transitive. If additionally ≤ is antisymmetric, then it is a partial order. Two elements x, y ∈ X are said to be incomparable if neither x ≤ y nor y ≤ x. An antichain in a quasi-order is a set of pairwise incomparable elements. A quasi-order (X, ≤) is a well-quasi-order if X contains no infinite strictly decreasing sequences and no infinite antichains.
According to the celebrated Graph Minor Theorem of Robertson and Seymour, the set of all graphs is well-quasi-ordered by the graph minor relation [13]. This, however, is not the case for the more restrictive relations such as subgraphs or induced subgraphs. Consider for instance the graphs H 1 , H 2 , . . ., where H i is the graph represented in Figure 1. It is not difficult to see that this sequence creates an infinite antichain with respect to both subgraph and induced subgraph relations.
By connecting two vertices of degree one having a common neighbour in H i , we obtain a graph represented on the left of Figure 2. Let us denote this graph by H ′ i . By further connecting the other pair of vertices of degree one we obtain the graph H ′′ i represented on the right of Figure 2.  We call any graph of the form H i , H ′ i or H ′′ i an H-graph. Furthermore, we will refer to H ′′ i a tight H-graph and to H ′ i a semi-tight H-graph. In an H-graph, the path connecting two vertices of degree 3 will be called the body of the graph, and the vertices which are not in the body the wings.
Following standard graph theory terminology, we call a chordless cycle of length at least four a hole. Let us denote by C the set of all holes and all H-graphs.
It is not difficult to see that any two distinct (i.e. non-isomorphic) graphs in C are incomparable with respect to the induced subgraph relation. In other words, Claim 1. C is an antichain with respect to the induced subgraph relation.
Moreover, from the poof of Theorem 4 we will see that for subquadratic classes of unbounded tree-width this antichain is unavoidable, or canonical, in the terminology of [6]. Suggested by this observation, we introduce the following definition. Definition 1. The graphs in the set C will be called canonical.
The order of a canonical graph G is either the number of its vertices, if G is a hole, or the the number of vertices in its body, if G is an H-graph.

Excluded graphs in subquadratic classes
It is obvious that any subquadratic class must exclude at least one complete graph and at least one complete bipartite graph, since the number of edges in these graphs is proportional to the square of the number of vertices. It turns out that this restriction is not only necessary but also sufficient for a hereditary class to be subquadratic. Theorem 1. Let X be a hereditary class. Then the following three statements are equivalent.
(1) X is subquadratic, (2) there exist numbers t and q such that K t / ∈ X and K q,q ∈ X, (3) there exists a number p such that no graph in X contains K p,p as a subgraph (not necessarily induced).
Proof. The implication (1)→(2) is obvious, since classes containing all cliques or all bicliques are not subquadratic. The implication (2)→(3) follows with p equal R(2, 2, max(t, q)), where R is the Ramsey number. Now let us show that (3) implies (1). Let Z r,s (n 1 , n 2 ) be the Zarankiewicz number, i.e. the smallest integer k such that every bipartite graph that has n 1 vertices on one side of its bipartition, n 2 vertices on the other side, and k edges contains a subgraph isomorphic to K r,s . Kővári, Sós and Turán [12] showed that From this we conclude that the number of edges in n-vertex graphs in X is less than 4pn 2−1/p . Indeed, assume to the contrary that an n-vertex graph G ∈ X contains at least 4pn 2−1/p edges. Then it must contain a bipartite subgraph G ′ (not necessarily induced) with at least 2pn 2−1/p edges. Let n 1 and n 2 be the number of vertices in the two parts of G ′ . Since n 1 < n, n 2 < n and (p − 1) 1/p < 2, we conclude with the help of the above bound on the Zarankiewicz number that By the definition of the Zarankiewicz number, this implies that G ′ , and hence G, contains a subgraph isomorphic to K p,p , contradicting (3). Therefore, (3) implies that the number of edges in n-vertex graphs in X is less than 4pn 2−1/p , i.e. X is subquadratic.

Long paths in graphs in subquadratic classes
In this section, we prove that graphs in a subquadratic class containing a large path also contain a large induced (i.e. chordless) path. We start with the following auxiliary result, where by P (r, m), we denote the minimum n such that in every coloring of the elements of an n-set with r colors there exists a subset of m elements of the same color (the pigeonhole principle). Lemma 1. For each p and q there is a number C = C(p, q) such that whenever a graph G contains two families of sets A = {V 1 , V 2 , . . . , V C } and B = {W 1 , W 2 , . . . , W C } with all sets being disjoint of size p and with at least one edge between every two sets V i ∈ A and W j ∈ B, then G contains a biclique K q,q .
Proof. We define r := P (p q , q) and C(p, q) := P (p r , q) and consider an arbitrary collection A of r sets from A. Since each set in B has a neighbor in each set in A, the family of the sets in B can be colored with at most p r colors so that all sets of the same color have a common neighbor in each of the r chosen sets of collection A. By the choice of C(p, q), one of the color classes contains a collection B of at least q sets. For each set in A, we choose a vertex which is a common neighbor for all sets in B and denote the set of r chosen vertices by U . The vertices of U can be colored with at most p q colors so that all vertices of the same color have a common neighbor in each of the q sets of collection B. By the choice of r, U contains a color class U 1 of least q vertices. For each set in B, we choose a vertex which is a common neighbor for all vertices of U 1 and denote the set of q chosen vertices by U 2 . Then U 1 and U 2 form a biclique K q,q .
Theorem 2. For every s and q there is a number Y = Y (s, q) such that every graph with a path of length at least Y contains either a path P s as an induced subgraph or a biclique K ⌊q/2⌋,⌈q/2⌉ as a (not necessarily induced) subgraph.
Proof. We use induction on s and q. For s = 1 and arbitrary q or for q = 1 and arbitrary s, we can take Y (s, q) = 1. So assume s > 1 and q > 1. Let t = Y (s, q − 1) and k = Y (s − 1, C(t, q)). Both numbers must exist by the induction hypothesis.
Consider a graph G with a path P = v 1 v 2 . . . v kt on kt vertices and split P into k subpaths on t vertices each. We denote the vertices of the i-th subpath by V i and form a graph H on k vertices {h 1 , h 2 , . . . , h k } in which h i h j is an edge if and only if there is an edge in G joining a vertex of V i to a vertex of V j . Since h i is joined to h i+1 for each i = 1, . . . , k − 1, the graph H has a path on k vertices, and since k = Y (s − 1, C(t, q)), it has either an induced path on s − 1 vertices or a biclique of order C(t, q). In the graph G, the latter case corresponds to two families of C(t, q) pairwise disjoint subsets with t vertices in each subset and with an edge between any two subsets from different families. Therefore, Lemma 1 applies proving that G contains a biclique K q,q . Now assume H contains an induced path P s−1 . In the graph G, this path corresponds to an ordered sequence of subsets V i 1 , V i 2 , . . . , V i s−1 with edges appearing only between consecutive subsets of the sequence. Therefore, in the subgraph of G induced by these subsets, any vertex v in V i 1 is of distance at least s − 2 from any vertex u in V s−1 . If the distance between v and u is s − 1, the graph G has an induced path P s and we are done. So, assume the distance between any two vertices of V i 1 and V i s−1 is exactly s − 2, and consider a path with exactly one vertex w p in each V ip .
If vertex w 1 has a neighbour w ∈ V i 1 which is not adjacent to w 2 , then ww 1 w 2 . . . w s−1 is an induced path P s and we are done. Therefore, we must assume that w 2 is adjacent to every vertex of V i 1 , since this set induces a connected subgraph. As the size of V i 1 is t = Y (s, q − 1), it contains either an induced path P s , in which case we are done, or a biclique K ⌊(q−1)/2⌋,⌈(q−1)/2⌉ . In the latter case, the biclique together with w 2 form a biclique of the desired size K ⌊q/2⌋,⌈q/2⌉ , so we are done as well. This completes the proof.
Taking into account that a large biclique gives rise either to a large induced biclique or a large clique, Theorem 2 can also be restated as follows.
Theorem 3. For every s, t, and q, there is a number Z = Z(s, t, q) such that every graph with a path of length at least Z contains either P s or K t or K q,q as an induced subgraph.

Main result: WQO classes of bounded treewidth
As we mentioned in the introduction, Daligault, Rao and Thomassé conjectured in [4] that every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. In the present section, we verify this conjecture for subquadratic classes. Moreover, we prove an even stronger result stating that every subquadratic class which is well-quasi-ordered by the induced subgraph relation is of bounded tree-width. Together with the well-known fact that the tree-width of cliques and bicliques is not bounded, we obtain the following dichotomy result. As we just mentioned, the "only if" part of this theorem readily follows from known facts. The rest of this section will be devoted to the proof of the "if" part, which will be given through a series of intermediate results.
In the proof, we use the terminology introduced in Section 2. A plan of the proof is outlined in Section 3.1. Sections 3.2, 3.3, 3.4, 3.5, 3.6 contain various parts of the proof.

Plan of the proof
To prove Theorem 4 we will show that graphs with arbitrarily large tree-width contain either arbitrarily large bicliques as subgraphs or arbitrarily large canonical graphs as induced subgraphs. The main notion in our proof is that of a rake-graph.
A rake-graph (or simply a rake) consists of a chordless path, the base of the rake, and a number of pendant vertices, called teeth, each having a private neighbour on the base. The only neighbour of a tooth on the base will be called the root of the tooth, and a rake with k teeth will be called a k-rake. We will say that a rake is ℓ-dense if any ℓ consecutive vertices of the base contain at least one root vertex. An example of a 1-dense 9-rake is given in Figure 3. 1. In Section 3.2, we observe that any graph of large tree-width contains a rake with many teeth as a subgraph.

t t t t t t t t t t t t t t t t t t t t
2. In Section 3.3 we show that any graph containing a rake with many teeth as a subgraph contains either -a dense rake with many teeth as a subgraph or a large canonical graph as an induced subgraph.

In Section 3.4 we prove that dense rake subgraphs necessarily imply either
a large canonical graph as an induced subgraph or a large biclique as a subgraph.
4. In Section 3.5, we summarize the results of the previous sections to show that any graph of large tree-width contains either a large canonical graph as an induced subgraph or a large biclique as a subgraph.
5. In Section 3.6, we use the result of Step 4 to prove Theorem 4.

Rake subgraphs in graphs of large tree-width
Lemma 2. For any natural k, there is a number f (k) such that every graph of tree-width at least f (k) contains a k-rake as a subgraph.
Proof. A k × k-grid is a graph with vertices v i,j 1 ≤ i, j, ≤ k and edges between v i,j and v i ′ ,j ′ if and only if |i − i ′ | + |j − j ′ | = 1. Clearly, every k × k-grid contains a k-rake as a subgraph. Moreover, any subdivision of a k × k-grid contains a k-rake as a subgraph.
In [14], Robertson, Seymour and Thomas proved that for each k there is a function f (k) such that every graph G of tree-width at least f (k) has a k × k-grid as a minor. Therefore, G contains a subdivision of a k × k-grid as a subgraph. As a result, G contains a k-rake as a subgraph.

From rake subgraphs to dense rake subgraphs
The main result of this section is Lemma 4 below. Its proof is based on the following auxiliary result. Proof. Let w ′ be a left wing and w ′′ a right wing of H * and U = {u 1 , . . . , u q } its body. Since w ′ is adjacent to u 1 and w ′′ is adjacent to u q , there must exist a sub-path U ′ = {u i , . . . , u i+k } of U such that u i is the only neighbour of w ′ in U ′ and u i+t is the only neighbour of w ′′ in U ′ . We assume that w ′ , w ′′ , U ′ are chosen so that t (the length of the path U ′ ) is as small as possible. This implies, in particular, that no other wing has an internal neighbor in U ′ (i.e. a neighbor different from u i and u i+t ). If 0 ≤ t ≤ s − 1, then w ′ U ′ w ′′ is a path satisfying (1). Assume now k ≥ s. If i = 1, we define u i−1 to be the left wing different from w ′ , and if i + t = q, we define u i+t+1 to be the right wing different from w ′′ . If w ′ is adjacent to w ′′ or w ′ is adjacent to u i+t+1 or w ′′ is adjacent to u i−1 , then a chordless cycle of length at least s + 1 arises. Otherwise, the vertices w ′ , w ′′ , u i−1 , u i , . . . , u i+t , u i+t+1 induce a canonical graph of order at least s. Lemma 4. Let k and s be natural numbers. Every graph containing a k + 2-rake as a subgraph contains either • an s + 5-dense k-rake a subgraph or • a canonical graph of order at least s as an induced subgraph.
Proof. Consider a graph G containing a k-rake R as a subgraph. For our construction it is essential that the second and second last vertices of the base of R are roots while the first and the last vertices are not. To establish this condition we remove the teeth whose roots are the first or the last vertices and possibly shorten the base so that it would start just before the next root and end just after the second last root. This is where k + 2 comes from. After this preprocessing, we proceed as follows.
First, we transform any path between any two consecutive root vertices into a shortest, and hence a chordless, path by cutting along any possible chords. Now any two consecutive root vertices together with their teeth, with the path connecting them and with two other their neighbours in the base of R form an H-graph satisfying conditions of Lemma 3. If one of these H-graphs contains an induced canonical subgraph of order at least s, the lemma is proved. Therefore, we assume that the wings of each of these graphs are connected by a short path as in (2) of Lemma 3. We now concatenate (glue) all these paths into the base of a new rake as follows.
Consider three consecutive vertices u i−1 , u i , u i+1 in the base of R with u i being a not the first root vertex. Let v i be the tooth of u i . Also, denote by P l a short path connecting two wings of the H-graph on the left of u i , and by P r the respective short path in the H-graph on the right of u i . To simplify the discussion, we will assume that if P r starts at u i−1 , then its next vertex is neither u i nor u i+1 , since otherwise we can transform P r by starting it at v i , which will increase the length of the path by at most 1. Also, we will assume that if P r starts at v i , then its next vertex is not u i+1 , since otherwise we can transform P r by adding u i between v i and u i+1 , which will increase the length of the path by at most 1. We apply similar (symmetric) assumptions with respect to P l . With these assumptions in mind, we now do the following.
• If both P l and P r contain u i , then both of them start at v i (according to the above assumption). In this case, we glue the two paths at u i , define it to be a root vertex in the new rake and define v i to be its tooth.
• Assume P l contains u i (implying it contains v i ), while P r does not. Assume in addition that P l contains u i−1 .
-If P r starts at u i−1 , then we glue the two paths at u i−1 (by cutting u i and v i off P l ), define u i−1 to be a root vertex and u i to be its tooth in the new rake.
-If P r starts at v i , then we glue the two paths at v i , define u i to be a root vertex and u i+1 to be its tooth in the new rake.
• The same as in the previous case with the only difference that P l does not contain u i−1 , -If P r starts at u i−1 , then we replace v i by u i−1 in P l , glue the two paths at u i−1 , define u i to be a root vertex and v i to be its tooth in the new rake.
-If P r starts at v i , then (like in the previous case) we glue the two paths at v i , define u i to be a root vertex and u i+1 to be its tooth in the new rake.
• Assume that neither P l nor P r contains u i , then we distinguish between the following cases.
-If both paths start at v i , then we glue them at v i , define it to be a root vertex and u i its tooth in the new rake.
-If one of them, say P l , starts at v i , and the other, i.e. P r , at u i−1 , then we concatenate them by adding u i (which is adjacent to both v i and u i−1 ), define u i to be a root vertex and u i+1 its tooth in the new rake.
-If P l starts at u i+1 P r starts at u i−1 , then we again concatenate them by adding u i , define u i to be a root vertex and v i its tooth in the new rake.
The procedure outlined above creates a new rake with k teeth. The length of each paths used in the construction is initially at most s + 1. In order to incorporate the assumptions regarding P l and P r we increase them by at most 1 on each end, so the resulting length is at most s + 3. Finally, the process of assignment of roots may require further increase by at most 1 on each end. Hence, we conclude that the new rake is s + 5-dense.

Dense rake subgraphs
Lemma 5. For every s, q and ℓ, there is a number D = D(s, q, ℓ) such that every graph containing an ℓ-dense D-rake as a subgraph contains either • a canonical graph of order at least s as an induced subgraph or • a biclique of order q as a subgraph.
Consider a graph G containing an ℓ-dense D-rake R 0 as a subgraph. The base of this rake is a path P 0 of length at least D and hence, by Theorem 3, the base contains either a biclique of order at least q as a subgraph (in which case we are done) or an induced path P of length at least ℓc 2 . Let us call any (inclusionwise) maximal sequence of consecutive vertices of P 0 that belong to P a block. Assume the number of blocks is more than c. Take the first c of them and add to each of them the vertex of P 0 following the rightmost endpoint of the block as a tooth. This creates a c-rake with P being an induced base. If the number of blocks is at most c, then P 0 must contain a block of size at least ℓc, in which case this block also forms an induced base of a c-rake (since R 0 is ℓ-dense). We see that in either case G has a c-rake with an induced base. According to the definition of c, the c teeth of this rake induce a graph which has either a clique of size 2q (and hence a biclique of order q in which case we are done), or an independent set of size b. By ignoring the teeth outside this set we obtain a b-rake R with an induced base and with teeth forming an independent set.
Let us denote the base of R by U , its vertices by u 1 , . . . , u m (in the order of their appearances in the path), and the teeth of R by t 1 , . . . , t b (following the order of their root vertices).
Denote r := (q − 1)s q + 2 and consider two sets of teeth T 1 = {t 2 , t 3 , . . . , t r } and T 2 = {t b−1 , t b−2 , . . . , t b−r+1 }. By definition of r and b, there are 2sq other teeth between t r and t b−r+1 , and hence there is a set M of 2sq consecutive vertices of U between the root of t r and the root of t b−r+1 . We partition M into 2q subsets (of consecutive vertices of U ) of size s each and for i = 1, . . . , 2q denote the i-th subset by M i .
If each vertex of T 1 has a neighbour in each of the first q sets M i , then by the Pigeonhole Principle there is a biclique of order q with q vertices in T 1 and q vertices in M (which can be proved by analogy with Lemma 1). Similarly, a biclique of order q arises if each vertex of T 2 has a neighbour in each of the last q sets M i . Therefore, we assume that there are two vertices t a ∈ T 1 and t b ∈ T 2 and two sets M x and M y with x < y such that t a has no neighbors in M x , while t b has no neighbours in M y .
By definition, t a has a neighbour in U (its root) on the left of M x . If additionally t a has a neighbour to the right of M x , then a chordless cycle of length at least s arises (since |M x | = s and t a has no neighbors in M x ), in which case the lemma is true. This restricts us to the case, when all neighbours of t a in U are located to the left of M x . By analogy, we assume that all neighbours of t b in U are located to the right of M y . Let u i be the rightmost neighbour of t a in U and u j be the leftmost neighbour of t b in U . According to the above discussion, i < j and j − j > 2s. But then the vertices t a , t b , u i−1 , u i , . . . , u j , u j+1 induce an H-graph (possibly tight or semi-tight) of order more than s (the existence of vertices u i−1 and u j+1 follows from the fact that T 1 does not include t 1 , while T 2 does not include t b ).

Canonical graphs and bicliques in graphs of large tree-width
Theorem 5. For every s, q, there is a number X = X(s, q) such that every graph of tree-width at least X contains either • a canonical graph of order at least s as an induced subgraph or • a biclique of order q as a subgraph.
Proof. We define X(s, q) as X(s, q) := f (D(s, q, s + 5)+ 2), where f comes from Lemma 2 and D comes from Lemma 5. If a graph G has tree-width at least X(s, q), then by Lemma 2 it contains D(s, q, s + 5) + 2-rake R as a subgraph. Then, by Lemma 4, G contains either a canonical graph of order at least s as an induced subgraph, or an s + 5-dense D(s, q, s + 5)-rake as a subgraph. In the first case, the theorem is proved. In the second case, we conclude by Lemma 5 that G contains either a canonical graph of order at least s as an induced subgraph or a biclique of order q as a subgraph.

Proof of Theorem 4
Let Y be a hereditary class of graphs defined by a set of forbidden induced subgraphs M , and assume Y is well-quasi-ordered by the induced subgraph relation.
If Y is of bounded tree-width, then the set M of forbidden graphs must include a complete graph and a complete bipartite graph, since the tree-width is bounded neither for complete graphs nor for complete bipartite graphs. Therefore, Y is subquadratic, which proves the first part of the theorem.
Assume now that Y is subquadratic. Then there must exist q such that no graph in Y contains K q,q as a subgraph. Suppose by contradiction that Y contains an infinite sequence Y ′ of graphs of increasing tree-width. In this sequence, there must exists a graph G 1 of tree-width at least X(s, q), where X(s, q) is defined in Theorem 5 and s is an arbitrarily chosen constant. Then by Theorem 5 G 1 contains a canonical graph H 1 of order at least s. We denote the order of H 1 by s 1 and find in Y ′ a graph G 2 of tree-width at least X(s 1 + 1, q). G 2 must contains a canonical graph H 2 of order s 2 ≥ s 1 + 1, and so on. In this way, we construct an infinite sequence H 1 , H 2 , . . ., which form an antichain by Claim 1. This contradicts the assumption that Y is well-quasi-ordered by the induced subgraph relation and hence shows that Y is of bounded tree-width.

Byproduct: Deciding WQO for subquadratic classes
In this section, we analyze the following problem. Given a finite collection of graphs G 1 , . . . , G k , decide whether the class of (G 1 , . . . , G k )-free graphs is well-quasi-ordered by induced subgraphs or not.
Decidability of this problem for two forbidden induced subgraphs was shown in [9]. This problem was also studied for the pattern containment relation on permutations [2], the embeddability relation on tournaments [3], the minor ordering of matroids [8], however, the decidability was shown only for one or two forbidden elements (permutations, tournaments, matroids). Whether this problem is decidable for larger numbers of forbidden elements is a big open question. In this section, we answer this question positively for the induced subgraph relation in subquadratic classes of graphs.
Theorem 6. Let X be a subquadratic class of graphs defined by a finite collection F of forbidden induced subgraphs. Then X is well-quasi-ordered by the induced subgraph relation if and only if F contains a path P k .
Proof. If F does not contain a path P k , then X contains infinitely many cycles, because by forbidding finitely many graphs we can exclude only finitely many cycles from X.
Assume now that F contains a path P k . Since X is subquadratic, F must also contain a clique and a biclique. But then, by Theorem 3, graphs in X do not contain large paths as subgraphs. In other words, there is a constant t such that X is a subclass of the class Y containing no P t as a subgraph. In [5], Ding showed that a class of graphs closed under taking subgraphs is well-quasi-ordered by the induced subgraph relation if and only if it contains finitely many cycles and finitely many graphs of the form H i . According to this result, Y , and hence X, is well-quasi-ordered by induced subgraphs.