Laurent Feuilloley
email: feuilloley@dii.uchile.cl

Michel Habib
email: habib@irif.fr

Graph classes and forbidden patterns on three vertices

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy hardly ever leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal.

. We improve on these two lines of works, by characterizing systematically all the classes defined by sets of forbidden patterns (on three nodes), and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time.

Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating.

Introduction

Forbidden structures in graph theory. A class of graphs is hereditary if for any graph G in the class, every induced subgraph of G also belongs to the class. Given a hereditary class C, there exists a family F of graphs, such that a graph G belongs to C, if and only if, G does not contain any graph of F as an induced subgraph. Hence hereditary classes are defined by forbidden structures. For a given class C, a trivial family F is the set of all graphs not in C, but the interesting families are the minimal ones. If we were to replace the induced subgraph relation by the minor relation, a celebrated theorem of Robertson and Seymour states that these families are always finite, but here the family needs not be finite, as exemplified by bipartite graphs (where the set of forbidden structures is the set of odd cycles). There exist many characterizations of classes by forbidden subgraphs in the literature, ranging from easy to extremely difficult to prove, as for example the Strong Perfect Graph Theorem [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF].

Forbidden ordered structures. Another way of defining hereditary classes by forbidden structures is the following. Consider a graph H given with a fixed ordering on its vertices. Then a graph G belongs to the class associated with H, if and only if, there exists an ordering of the vertices of G, such that none of its subgraphs induces a copy of H with the given ordering. Let us illustrate such characterization with chordal graphs. Chordal graphs are usually defined as the graphs that do not contain any induced cycle of length at least 4. However it is also well known [START_REF] Dirac | On rigid circuit graphs[END_REF] that chordal graphs are exactly the graphs that admit a simplicial elimination ordering, that is an ordering on the vertices such that the neighbors of a vertex that are placed before it in the ordering induce a clique. In the framework described above, this characterization corresponds to H being the path on 3 vertices with the middle vertex placed last in the ordering. Similar characterizations are known for well-studied classes such as proper interval, interval, permutation and cocomparability graphs.

We focus on such characterizations, and refer to forbidden ordered induced subgraphs (or more precisely an equivalent trigraph version of it) as patterns.

Forbidden patterns and algorithms. A motivation to study characterizations by patterns is that they are related to efficient recognition algorithms. That is, unlike forbidden subgraph characterizations, forbidden patterns characterization often translate into fast algorithms to recognize the class, most of the time linear-time algorithms. Such algorithms compute an ordering avoiding the forbidden patterns, which means that in addition of deciding whether the graph is in the class or not, they provide a certificate for the positive cases. The most famous examples are for chordal graphs [67], proper interval graphs [START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF], and interval graphs [START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF].

These algorithms are fast because they use simple graph searches, in particular the lexicographic breadth first search, LexBFS. Indeed the orderings given by searches have a special structure [START_REF] Corneil | A unified view of graph searching[END_REF], that matches the one of forbidden patterns.

Previous works on forbidden patterns. The papers [START_REF] Skrien | A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs[END_REF] and [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF] by Skiren and Damaschke respectively are, as far as we know, the first works to consider characterizations by patterns as a topic in itself. From these seminal papers, one can derive that all the classes defined by one forbidden pattern on three node can be recognized in polynomial time. This is for example the case for the chordal graphs mentioned above. More recently, it was proved that forbidding a set of patterns on three nodes, still leads to a polynomially solvable problem [START_REF] Hell | Ordering without forbidden patterns[END_REF]. This stands in striking contrast with the case of larger patterns, as it was shown in [START_REF] Duffus | On the computational complexity of ordered subgraph recognition[END_REF] that almost all classes defined by 2-connected patterns are NP-complete to recognize. In [START_REF] Hell | Ordering without forbidden patterns[END_REF], the authors conjectured a dichotomy on this type of recognition problem, but this statement has been recently challenged [57].

More generally, forbidden ordered structures have been used recently in a variety of contexts. Among others, they have been applied to characterize graphs with bounded asteroidal number [START_REF] Corneil | Vertex ordering characterizations of graphs of bounded asteroidal number[END_REF], to study intersection graphs [START_REF] Wood | Characterisations of intersection graphs by vertex orderings[END_REF], to prove that the square of the line-graph of a chordal graph is chordal [5], and to study maximal induced matching algorithms [START_REF] Habib | Maximum induced matching algorithms via vertex ordering characterizations[END_REF].

Our results Forbidding only one pattern on three nodes already gives rise to a rich family of graph classes. Yet, despite the general algorithmic result of [START_REF] Hell | Ordering without forbidden patterns[END_REF], little is known about the classes defined by a set of patterns on three nodes. Our main contribution is an exhaustive list of all the classes defined this way. Along the way several interesting results and insights are gathered. A corollary of this characterization is that almost all the classes considered can be recognized not only in polynomial time, but in linear time. Beyond these technical contributions, our goal is to unify many results scattered in the literature, and show that this formalism can be useful and relevant. In this sense, the paper also serves as a survey of this type of hereditary classes of graphs.

Outline of the paper. The paper is organized as follows. In Section 2, we motivate the study of patterns by listing the well-known classes characterized by one pattern on three node. In Section 3, we formally define the pattern characterizations, and prove structural properties about the classes defined this way. Section 4 contains the main theorem of the paper, that is the complete characterization of all the classes defined by sets of patterns on three nodes. The proof of this theorem is a long case analysis, and to make it nicer, we first highlight and prove some remarkable characterizations in Section 5, before completing the proof in Section 6. In Section 7, we deal with the algorithmic aspects, in particular the linear-time recognition. Finally we discuss related topics and open questions in Section 8.

Appetizer: classes defined by one pattern

In this section, we introduce a few classes characterized by one pattern on three nodes. We do so before defining formally pattern characterizations, as an appetizer for the rest of the paper. All these characterizations are known, and in particular they are listed in [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]. 1 The main take-away of this short section is that essential graph classes can be defined by one pattern on three nodes, hence such characterizations are important.

Let us introduce a graphic intuitive representation of patterns. Consider the drawing of Figure 1.

Figure 1

The graphic representation of the pattern associated with the class of interval graphs. 1 For completeness we prove these characterizations in Section 5, as no proof can be found in [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF].

The class associated with this pattern is the class of graphs G = (V, E) that have an ordering of their vertices such that: there is no ordered triplet of nodes, a < b < c, such that (a, b) / ∈ E and (a, c) ∈ E. In other words, the forbidden configuration consists in a non-edge (dashed edge in the drawing) between the two first nodes, an edge (plain edge in the drawing) between the first and the last node, and there is no constraint (no edge in the drawing) on the edge between the second and the third node (that is, whether there is an edge or not, the configuration forbidden).

Theorem 1. ( [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]) In Table 1, each class of the first column is characterized by the pattern represented in the second column. (The third column is the name we give to this pattern.)

Graph class

Pattern representation Pattern name Linear forests Linear Forest

Stars

Star

Interval graphs Interval

Split graphs Split

Forest Forest

Bipartite graphs Bipartite

Chordal graphs Chordal

Comparability graphs Comparability

Triangle-free graphs Triangle-Free

At most two nodes No Graph

Table 1 The table of Theorem 1. For each row the class on the first column is characterized by the pattern represented in the second column, whose name is on the third column.

Definitions and structural properties

The current paper aims at doing a thorough study of the classes defined by patterns on three nodes, and of their relations. In this section we give the formal definitions and introduce structural properties of these classes. More precisely, we start in Subsection 3.1 by defining formally the patterns and related concepts, and in Subsection 3.7 by listing the definitions of the graph classes we will use. Then in Subsection 3.2 we define some basic operations on patterns and in Subsections 3.3, 3.5, and 3.6, we describe important structural properties of the classes defined by patterns.

Definitions related to patterns

In all the paper we deal with finite loopless undirected graphs, and multiple edges are not allowed. For such a graph G, we denote by V (G) the set of vertices and E(G) its set of edges, with the usual |V (G)| = n and |E(G)| = m for complexity evaluations. The graph we consider are not necessarily connected.

To define patterns, we use the vocabulary of trigraphs as, for example, in [START_REF] Chudnovsky | Berge trigraphs[END_REF].

Definition 1. A trigraph T is a 4-tuple (V (T ), E(T ), N (T ), U (T ))
where V (T ) is the vertex set and every unordered pair of vertices belongs to one of the three disjoint sets E(T ), N (T ), and U (T ), called the edges, non-edges and undecided edges, respectively. A graph

G = (V (G), E(G)) is a realization of a trigraph T if V (G) = V (T ) and E(G) = E(T ) ∪ U , where U ⊂ U (T ).
When representing a trigraph, we will draw plain lines for edges, dashed lines for non edges, and nothing for undecided edges. Also as (E, N, U ) is a partition of the unordered pairs, it is enough to give any two of these sets to define the trigraph, and we will often define a trigraph by giving only E and N . Definition 2. An ordered graph is a graph given with a total ordering of its vertices. A pattern is an ordered trigraph. An ordered graph is a realization of a pattern if they have the same set of vertices, with the same linear ordering, and the graph is a realization of the trigraph. When, in an ordered graph, no ordered subgraph is the realization of given pattern, the ordered graph avoids the pattern.

In this formalism, the pattern for interval graphs represented in Figure 1

is (E, N ) = ({(1, 3)}, {(1, 2)}).
For simplicity we give names to the patterns, related to the classes they characterize. These names are in capital letters to avoid confusion with the classes. For example the one of Figure 1 is called Interval. More generally, the names follow from Theorem 1. The list of the names of all the patterns is given in Figure 2. The pattern that have no undecided edge are called full patterns. Definition 3. Given a family of patterns F, the class C F is the set of connected graphs that have the following property: there exists an ordering of the nodes that avoids all the patterns in F.

To make these definitions more concrete, let us find out which classes are characterized by patterns on two nodes, V = {1, 2}. Forbidding the pattern (E, N ) = ({(1, 2)}, ∅) means that the graphs we consider have a vertex ordering such that there is no pair of nodes a < b with an edge (a, b). This implies that the graph has actually no edge thus this is the class of independent sets. Similarly forbidding the pattern (E, N ) = (∅, {(1, 2)}) leads to the cliques. Finally (E, N ) = (∅, ∅) corresponds to a trivial class: only the graph with one node does not have two nodes that are either linked or not by an edge.

Finally, if F consists of only one pattern P , we write P instead of {P }, thus C P instead of C {P } .

Operations on patterns and families

We define a few operations on patterns and pattern families. Definition 4. The mirror and complement operations are the following:

The mirror of a pattern is the same pattern, except for the vertex ordering, which is reversed. The mirror of a family F is the set of the mirrors of the patterns of the family, and is denoted by mirror-F. The complement of a pattern (V, E, N ) is the pattern (V , E , N ) with V = V , E = N , and N = E, that is, the pattern where the edges and non-edges have been exchanged. The complement of a family F is the set of the complements of the patterns of the family, and is denoted by co-F. A pattern P 2 is an extension of a pattern P 1 , if it can be obtained by taking P 1 , and having the possibility to add nodes and to decide undecided edges. A family F 2 extends a family F 1 , if every pattern of F 1 has an extension in F 2 , and every pattern in F 2 is an extension of a pattern in F 1 .

Basic structural properties

We now list some basic structural properties of the classes defined by forbidden patterns. Most of them also appear in [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]. We omit the proofs, as they follow directly from the definitions.

Property 1. The following properties hold for any pattern family F.

(Vertex closure)

The class C F is closed under vertex deletion, that is, is hereditary. Item 1 states that the classes defined by patterns are hereditary. The converse is also true (if we allow infinite families). Indeed any hereditary family has a characterization by a family of forbidden induced subgraphs, and such characterization can automatically be translated into a characterization by patterns: just take the union of all the orderings of all the forbidden subgraphs.

(Edge

Pattern names

In order to designate patterns in an efficient way, we gave them names and numbers described in Figure 2. The names are inspired by Theorem 1 and the basic operations of Subsection 3.3.

Pattern split rule

Let us now describe the pattern split rule, which is basically a rewriting rule, that we will use extensively. It states that a pattern that has an undecided edge can be replaced by two patterns (that is, can be split into two patterns): one where this edge is a (plain) edge, and one where it is a non-edge. Lemma 1. Let F be a pattern family. Let P = (V, E, N ) be a pattern of F, and e be an undecided edge of P . An ordered graph avoids the patterns of F, if and only if, it avoids the patterns of F , where F is that same as F except that P that has been replaced by P 1 = (V, E ∪ e, N ) and P 2 = (V, E, N ∪ e). Proof. It is sufficient prove the statement for the case where F is restricted to P , as the other pattern do not interfere. Consider a graph G, with an ordering τ . If (G, τ ) avoids the pattern P , then clearly τ avoids also the patterns P 1 , P 2 , since each occurence of a pattern P 1 or P 2 yields an occurence of pattern P . Reciprocally, if (G, τ ) avoids the patterns P 1 , P 2 then it also avoids the pattern P , since each possible occurence of pattern P in (G, τ ) must corresponds to either an occurence of pattern P 1 or of pattern P 2 .

As a consequence, with the notations of the lemma, we have C F = C F . By iterating the rule, one can always transform an arbitrary family of patterns into a family of full patterns. Actually the seminal papers on this topic, e.g. [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF], use only full patterns. In this paper, we choose to use undecided edges because they allow for compact notations and provide additional insights.

The notation P = P 1 &P 2 denotes that P can be split into P 1 and P 2 . For example, Interval = Chordal & co-Comparability. A family is split-minimal if there are no two patterns P 1 and P 2 in the family, such that there exists a third pattern P with P = P 1 &P 2 .

Union-intersection property

Item 5 of Property 1 states that C F1∪F 2 ⊆ C F1 ∩ C F2 . When the equality holds, we say that these classes have the union-intersection property. A trivial case of union-intersection property is when one family is included in the other. Here is a more interesting example. Using Lemma 1 and Item 5 of Property 1, we know that:

C Interval = C Chordal&co-Comparability ⊆ C Chordal ∩ C co-Comparability .
But it is known from the literature [START_REF] Gilmore | A characterization of comparability graphs and of interval graphs[END_REF] that the last inclusion is actually an equality: interval graphs are exactly the graphs that are both chordal and cocomparability. We will see several other cases where the union-intersection property holds. From the example above, it is tempting to conjecture that any time the pattern split rule applies, the unionintersection property holds, but this is actually wrong. For example Linear Forest=Forest & mirror-Interval thus C Forest&mirror-Interval is the class of linear forests, but C Forest ∩ C mirror-Interval is a larger class, as it contains any star (more details are given in Property 2).

A useful special case of Item 5 in Property 1 is the following:

Fact 1. Let F 1 , F 2 be two sets of patterns, if C F1 ⊆ C F2 , then C F1∪F2 ⊆ C F1 .
It should be noticed that C F1 ⊆ C F2 could derive from a structural graph theorem and not directly from the set of patterns. Furthermore, even in this restricted case, the unionintersection property does not always hold, as we will prove in Theorem 4, that {Forest, mirror-Forest} characterizes only paths.

Another special case, is when the patterns are stable by permutation of the ordering of the nodes. On three nodes only the patterns No Graph, Triangle-Free and co-Triangle-Free have this property. If one of the families at hand contains only pattern with this property, then the union-intersection property holds. Fact 2. Let F 1 , F 2 be two sets of patterns, if one of the two families contains only patterns that are stable by change of the ordering of the nodes, then C F1∪F2 = C F1 ∩ C F2 .

Graph classes

In this section, we define the graph classes we use. References on this topic are [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Hn De Ridder | Information system on graph classes and their inclusions (ISGCI)[END_REF]. In the remaining, we will use P i to refer to an induced path with i nodes, and C i refers to an induced cycle on i nodes.

For many classes we give several definitions. In addition to highlighting similarities between some of these classes, this will be helpful in the characterization proofs. For example, characterization by forbidden subgraph are helpful when proving that a set of patterns imply that the graph belong to a class. On the other hand an incremental of geometric construction usually provides a natural ordering to avoid the patterns at hand. Definition 5. The definitions of the main graph classes we use are the following: 1. A forest is a graph with no cycle.

2.

A linear forest is a disjoint union of paths.

3.

A star is a graph where at most one node has several neighbors. 4. An interval graph is the intersection graph of a set of intervals. That is, a graph on n vertices is an interval graph, if there exists a set of n intervals that we can identify to the vertices such that two intervals intersect if and only if the associated vertices are adjacent.

5.

A graph is a split graph if there exists a partition of the vertices such that the subgraph induced by the first part is a clique, and the subgraph induced by the second part is an independent set. Note that the split graphs are connected, except (possibly) for isolated nodes. 6. A graph is bipartite if there exists a partition of the vertices in 2 parts such that the 2 resulting induced subgraphs are independent sets. 7. A graph is chordal if it contains no induced cycle of length strictly greater than 3. 8. A graph is a comparability graph if its edges represent a partial order. That is, a graph on n vertices is a comparability graph if there exists a partial order with n elements that we can identify with the vertices, such that two elements are comparable if and only if they are adjacent in the graph. 9. A graph is triangle-free if it contains no clique of size 3.

10.

A permutation graph ([28]) is a graph whose vertices represent the elements of a permutation, and whose edges link pairs of elements that are reversed by the permutation. We will also consider bipartite permutation graphs, the subclass of the permutation graphs that are bipartite. 11. A threshold graphs is equivalently ( [START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF]53]):

a. a graph that can be constructed by incrementally adding isolated vertices and dominating vertices. b. a split graph without induced P 4 . c. a split graph where the neighborhoods of the nodes of the independent set and of the nodes of the clique are totally ordered. That is, a graph with vertex set V = I ∪ K, with I = {i 1 , ..., i p } an independent set and K = {k 1 , ..., k q } a clique, such that a. a graph in which, for every induced subgraph, the size of a maximum independent set is equal to the number of maximal cliques. b. a quasi-threshold graph, that is a graph that can be constructed recursively the following way: a single node is a quasi-threshold graph, the disjoint union of two quasi-threshold graphs is a quasi-threshold graph, adding one universal vertex to threshold graph gives a quasi-threshold graph. c. a (C 4 , P 4 )-free graph. d. a comparability graph of an arborescence, that is the comparability graph of a partial order in which for every element x, the elements of {y|y < x} can be linearly ordered. e. the intersection graph of a set of nested intervals (that is of intervals such that for every intersecting pair, one interval is included in the other).

N (i 1 ) ⊆ • • • ⊆ N (i p ) and N (k 1 ) ⊇ • • • ⊇ N (k q ).

A bipartite chain graph is equivalently ([72]):

a. a bipartite graph, for which, in each class, one can order the neighborhoods by inclusion.

That is, with a partition,

A, B, A = a 1 , . . . , a |A| satisfies N (a 1 ) ⊇ N (a 2 ), . . . , ⊇ N (a |A| ) and B = b 1 , . . . , b |B| satisfies N (b 1 ) ⊆ N (b 2 ) • • • ⊆ N (b |B| ). b. a difference graph, that is a graph where every node v can be given a real number k v in (-1, 1) such that (u, v) ∈ E if and only if |k u -k v | ≥ 1. c. a 2K 2 -free
bipartite graph, that is a bipartite graph that does not have two independent edges that are not linked by a third edge (i.e. no induced complement of a C 4 ).

There are 3 more classes that will appear for technical reasons in our results which are variants of the classes above. Definition 6. 1. A 2-star is a connected caterpillar with a dominating path of length at most 2, plus possibly isolated nodes.

2.

A 1-split is a graph which is either a clique or a clique minus one edge, or the complement of such a graph, that is an independent set, plus possibly an edge.

3.

An augmented clique is a clique, plus one additional node with arbitrary adjacency, plus possibly isolated nodes.

Connectivity issues.

A subtlety in the definitions of the classes is the connectivity of the graphs. For our work, there are basically two cases:

The classes that are stable by disjoint union: linear forests, interval graphs, bipartite graphs, chordal graphs, comparability graphs, triangle-free graphs, permutation graphs, proper interval, caterpillars, trivially perfect The classes that are stable only by addition of isolated vertices: stars, split graphs, threshold graphs, bipartite chain graphs, 2-stars, augmented clique.

Note that this classification depends on the class we chose to consider. That is, in this work we always consider both a class and its complement class, and for the complement classes the classification above becomes : stable by the join operation and by addition of a universal clique. Also in some cases, the class considered does not allow for isolated nodes, this is the case for 1-split for example.

Trivial classes. We used the word trivial for classes that are basically finite. Here is a more formal definition.

Definition 7.

A graph class G is called trivial if there exists a finite family of connected graphs F such that ∀G ∈ G every connected component of G is isomorphic to some graph in F .

We will use the following fact about these classes. Fact 3. Let C be a trivial graph class and P a pattern. The subclass of C consisting of the graphs that have a vertex ordering avoiding P , is also a trivial graph class.

Characterization theorem

We are now ready to state our main theorem. We refer to basic operations for addition of isolated nodes, and restriction to connected component.

Theorem 2. Up to complement and basic operations, the non-trivial classes that can be characterized by a set of patterns on three vertices are the following.

complete bipartite

Let us first say a few words about the proof, and then comment on this theorem.

Proof outline. To prove the theorem, we first generate all the split-minimal pattern families. This is basically done by listing all the possible sets of patterns, and then simplifying it, with the help of a program (that is presented in Subsection 6.1). The simplification step consists of removing the complement, mirror, complement-mirror families, and applying the pattern split rule until we get split-minimal families. After this step, we get the following result.

Lemma 2. Up to complementation and mirroring, there exist 87 split-minimal families of patterns on three vertices.

The proof of the theorem consists in a case analysis: for each set of patterns of the list given by Lemma 2, we find the class that is characterized by this set. Roughly our approach is in three steps. First, we check whether the set of patterns is known to characterize a class. This works for the patterns of Theorem 1 for example. If not, the second step is to use the structural properties of Section 3 along with the class already characterized to get a candidate class. Sometimes this is enough, and we can conclude. Third, we work on the set of patterns, to get the class. Interestingly, for this last step, knowing various characterizations of a same class, as presented in Subsection 3.7, does help.

Comments on Theorem 2

The first comment to make is that there are only 22 classes in the list. The naive upper bound on the number of classes is 2 3 3 = 2 27 , thus having only 22 non-trivial classes (up to complement and basic operations) at the end is a surprising outcome. This is first explained by the fact that many sets of patterns are equivalent (because of the mirror, complement, and pattern split rules) as witnessed by Lemma 2. (As will be explained later, when looking for the number of classes only, one can restrict to a set of eight patterns, thus the upper bound already falls to 2 8 = 256, and further refinements makes the list go down to 87.) Also many classes end up being trivial because they have patterns that are somehow conflicting. For example Theorem 3 will show that in most cases, having a pattern and its complement in a family directly lead to a trivial class. Finally, some classes, like threshold graphs appear several times in the proof, as they correspond to various sets of patterns.

A second surprising fact is the large majority of the classes listed are well-known classes. This supports the insight of Theorem 1, that characterizations by patterns arise naturally in the study of graph classes.

Third, we phrased the theorem as a list, but the result is somehow richer. Indeed these classes form an interesting web of inclusions, and there is a lot to say about the relations between the classes. These inclusions are represented in Figure 3. (The inclusions that are not known or do not follow directly from Property 1, are proved within the proof of the theorem.)

Highlighted classes and characterizations

Among the sets of patterns on three nodes, some stand out because of their particular structures. These are, for example, the pairs of patterns that are mirror of one another.

In this section, we study such special cases, anticipating on Theorem 2. We start in Subsection 5.

Classes defined by one pattern

In this subsection, we consider the classes defined by one pattern. There are exactly 3 3 = 27 different patterns on three nodes, as listed in Figure 2.

We first prove Theorem 1.

Proof of Theorem 1. For each class, when the characterization is not explicitly known, we first prove that it satisfies the forbidden pattern property by exhibiting the ordering, and then we show the other inclusion. Note that most of the graphs considered can be disconnected. Linear Forest. (→) If the graph is a linear forest that is a disjoint union of paths, then the natural ordering avoids the pattern. That is, placing the paths one after the other, from one endpoint to the other, avoids any jump over a node.

In the other direction, we first claim that if an ordering avoids the pattern, then every vertex has degree at most 2. Indeed if a node has three or more neighbors, there must be at least two in the same direction (to the right or to the left), and then the pattern appears. Second, it is clearly not possible to avoid the pattern with a cycle. Thus we are left with the paths.

Star. In this paper, a star is a graph where at most one node has neighbors. This The edges labeled with "co" mean: the family made by taking the pattern on the top endpoint and its complement characterize the class below. The edges labeled with "mi" mean the same but with mirror instead of complement. And "co-mi" designate both operations. The + means that the edge has both labels.

basically means that the nodes of a star can be partitioned into two sets L and I and a special node c, and the edge set is the union of the (c, ) for any ∈ L. (→) Any ordering with the nodes of I, then the nodes of L and then c avoids the pattern. (←) Only the rightmost node can have an edge going left. Thus if we remove this node the graph is has no edges. This node is c in our characterization, and its neighbors and non-neighbors define L and I respectively.

Interval. This characterization is well-known for interval graphs, and an ordering avoiding this pattern is sometimes called a left-endpoint ordering, see [START_REF] Olariu | An optimal greedy heuristic to color interval graphs[END_REF][START_REF] Ramalingam | A unified approach to domination problems on interval graphs[END_REF].

Split. Remember that a split graph is a graph that can be partitioned into an independent set and a clique. Note that there might be isolated nodes, belonging to the independent set. (→) Any ordering of the following form avoid the pattern: first the isolated nodes, then the nodes from the independent set, and then the nodes from the clique. (←) Consider the node v that is the first node in the ordering to be the right-end of an edge, and let u be the left end-point of such an edge. In order to avoid the pattern, the graph must contain all the edges (v, w) with v < w. Iteratively, we deduce that the graph contains all the edges (a, b) with v ≤ a < b. Therefore v < ... < n is a clique. Also by minimality, the nodes 1 < ... < v -1 form an independent set. Hence the graph has a split partition.

Forest. (→) Consider the ordering τ given by any generic search applied on G, as defined in [START_REF] Corneil | A unified view of graph searching[END_REF]. Suppose such τ contains the forbidden pattern on a < τ b < τ c with ac, bc ∈ E(G). Then using the four points condition of generic search, there must exist a vertex d < τ b, with db ∈ E(G) and a path joining a to d with vertices before d in τ . This implies that there is a cycle in the graph, which is impossible as we started with a forest. Thus the pattern is not present. (←) Consider a graph and any ordering τ of the vertices. Every cycle of the graph has a last vertex x with respect to τ . This vertex x has necessarily two neighbours to its left in τ , which corresponds to the forbidden pattern.

Bipartite. (→) Consider an ordering where the different connected components are placed one after the other. The pattern can only appear inside a component. Then for each component (that is bipartite) the vertices of one independent set are all placed before the vertices of the other independent set. All the vertices of the first set have all their edges pointing to the right, and all the vertices of the second set have all their edges pointing to the left. As a consequence no vertex has edges pointing both to the left and to the right, therefore the pattern does not appear. (←) Consider an ordering of a graph avoiding the pattern. If the graph has no cycle, then it is bipartite. Consider now an induced cycle. Because of the forbidden pattern, the nodes of this cycle can be partitioned into two sets: the ones that are adjacent (in the cycle) to two nodes on their left, and the nodes that are adjacent (in the cycle) to two nodes on their right. Because any edge must have an endpoint in each set, the two sets must have the same size, and the cycle must have even length. Thus the graph is bipartite. 2Chordal. This characterization is well-known, and the ordering is usually called simplicial elimination ordering [START_REF] Delbert | Incidence matrices and interval graphs[END_REF]. 3Comparability. By definition an ordered graph avoids the forbidden pattern, if and only if, the ordering is a linear extension of a partial order. The fact that the complement pattern (sometimes called umbrella) defines cocomparability graphs has been noted in [START_REF] Kratsch | Domination on cocomparability graphs[END_REF].

Triangle-Free. For patterns that are stable by any change of the ordering of the vertices, such as triangles, the forbidden pattern characterization boils down to the associated forbidden induced subgraph characterization.

At most two nodes. The pattern is made of three nodes, with no plain or dashed edge. Then every ordered graph with three or more nodes contains the pattern. Thus the class is trivial: it consist only in the graphs with one or two nodes.

The following corollary states that, up to complement, the classes defined by one pattern are exactly the ones listed in Theorem 1.

Corollary 1. Up to complementation the ten graph classes described in Theorem 1, are the only ones that can be defined with exactly one forbidden pattern on three nodes.

Proof. We prove the statement in the following way: we count the number of different patterns obtained from the ones in Table 1 by complementation and mirror, and check that we reach the total number, which is 27. Hence we start with the 10 patterns of Table 1. All the patterns except the pattern No Graph, have a complement that is not already in the list, thus we get to 19 patterns. Now for the mirror, four patterns are self-mirrors (Comparability, Triangle-Free, Bipartite and Linear Forest), thus these do not add new patterns. The pattern Split has a mirror that is the same as its complement. Therefore we add only four mirror patterns, and get 23. Finally, these four patterns have complements that are not in the list yet. And this completes the landscape of 27 patterns. Now, something interesting is the relations of these classes. It happens that in many cases the union-intersection property (as described in Subsection 3.6) holds, which implies a neat hierarchy of inclusions represented in Figure 4. The following lemma lists the cases of pattern split rule, and highlights the ones where the union-intersection property holds. In some cases we know it holds from the literature, and in some others, it is folklore. For the four first items, the union-intersection property holds, and for completeness we prove that it does not hold for the last two items. For these items, the intersection of the classes is strictly larger than the class with the 'unsplit' pattern. Proof. We prove the three items.

1. From Item 13 of Definition 5, caterpillars are the (T 2 , cycle)-free graphs. It is known that interval graphs also have a characterization by forbidden subgraphs [START_REF] Lekkeikerker | Representation of a finite graph by a set of intervals on the real line[END_REF], and the only cycle-free subgraph in the list is T 2 . Thus cycle-free interval graphs are exactly the caterpillars. 2. Consider a split graph and its partition into a clique K and an independent set I. If the graph is bipartite, then K has size at most two, as otherwise there would be a triangle.

Then every node of the independent set can be connected to at most one of these clique nodes, for the same reason. This corresponds to a 2-star. The reverse inclusion is trivial, using the same partition. 3. By definition a 2-star is cycle-free. We show that it is also a co-interval graph. Let (a, b)

be the dominating edge of the 2-star, S a be the leaves of a, and S b be the leaves of b. Also let I be the set of isolated nodes. Now we complement the graph. It has the following shape. The nodes of I are connected to all the nodes, there is a complete bipartite graph between S a and S b , a is connected to every node of S b , b is connected to every node of S a , and finally S a and S b are cliques. This can be represented by a set of closed intervals: b is [0, 1], all the nodes of S a are [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF], all the nodes of S b are [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Bernhart | The book thickness of a graph[END_REF], a is [START_REF] Bernhart | The book thickness of a graph[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF], and the nodes of I are [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF]. Thus a 2-star is a co-interval graph. Now we prove that cycle-free co-interval graphs are 2-stars. First note that a graph of the class cannot have two independent edges (that is a 2K 2 ). Indeed the complement of two independent edges is a 4-cycle, and interval graphs are C 4 -free. Thus, except for isolated nodes, the graph can have only one connected component. Also, as in a tree if the diameter is more than 3, then there are two independent edges. Therefore the connected component must be a tree of diameter at most 3, and this matches the definition of a 2-star.

Complementary patterns

We now consider families of the type {P 1 , P 2 }, where P 1 and P 2 are complementary patterns. Proof. 1. First notice that the patterns Triangle-Free and co-Triangle-Free are invariant by permutation of the vertices, thus excluding these patterns is a matter of induced subgraphs more than a matter of patterns. It is known that any graph with at least six nodes has either a triangle or an independent set of size three (because the Ramsey number for these parameters is 6). Therefore only graphs with at most 5 vertices can belong to the class. The class is then trivial.

2.

It is known that the intersection of the classes of comparability and co-comparability graphs is the class of permutation graphs [START_REF] Dushnik | Partially ordered sets[END_REF]. Thus the class of Comparability & co-Comparability is included in the class of permutation graphs, by Item 5 of Property 1.

We use the literature to show that this inclusion is an equality. The 2-dimensional orders, which are transitive orientations of permutation graphs, were characterized in [START_REF] Dushnik | Partially ordered sets[END_REF], by the existence of a non-separating linear extension. Such extension happens to be exactly an ordering avoiding the patterns Comparability and co-Comparability. 3. This result appears without proof in [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]. We provide a proof for completeness.

As written in Lemma 3, the intersection of chordal graphs and co-chordal graphs, is the class of split graphs. But the class of the union of the two patterns is smaller. Indeed, a split graph can have a P 4 , and it is easy to check that no ordering of a P 4 can avoid the two patterns (see Figure 6). The split graphs that have no P 4 are the threshold graphs (Item 11b in Definition 5). Thus the direct inclusion holds. We now build an ordering of any threshold graph, that avoids both patterns. Note that an ordering τ avoids both patterns if and only if the reverse ordering of τ is a simplicial elimination ordering for both G and G. We will build such an ordering, using the following claim.

Claim 1. For any threshold graph there exists a partition of the vertices V = x ∪ I ∪ K, such that I is an independent set, K is a clique, and x is adjacent to every node in K and no node in I.

Proof. A partition V = K ∪ I exists for any threshold graphs, as they are split graphs. It is sufficient to find a proper node x. Consider the node of I that has the largest neighborhood inclusion-wise (it is well-defined, thanks to Item 11c of Definition 5). If this neighborhood is K, then this node can be taken as x. Otherwise there exists a node of K that has no neighbor in I and it can be taken as x.

The node x of Claim 1 is simplicial in both G and G. We can take it as the first vertex. Since threshold graphs form a hereditary class, we can repeat the argument on G -x. Therefore, every threshold graph admits a vertex ordering which is a simplicial elimination scheme of both G, G. The reverse of this ordering avoids both patterns.

The class defined by Interval & co-Interval is included in the class defined by Chordal

& co-Chordal because of Item 6 of Property 1. Therefore this class is included in the threshold graphs.

For the other direction, we show that any threshold graph admits an ordering that avoids the patterns Interval and co-Interval. Using the pattern split rule, it is equivalent to find an ordering avoiding the patterns Chordal, co-Chordal, Comparability and co-Comparability. The ordering of the previous item avoids Chordal, co-Chordal. We show that it also avoids Comparability and co-Comparability. By complement, it is sufficient to show that the ordering avoids Comparability. Consider the reverse ordering where we added the nodes x, from left to right (this is harmless for the comparability pattern, as it is symmetric). We remark that in this ordering, the nodes that are part of the independent set in the original partition, have no neighbor to their left. Indeed when such a node is taken in the ordering, its full neighborhood is still present in the graph. Thus if the pattern appears, the first node must be part of the independent set, and the other nodes part of the clique. But this is impossible, as the nodes of the clique that are to the right of a node of the independent set must both be linked to this node. 5. The only vertex orderings of a split graph that satisfy the Split pattern start with an independent set and finish with a clique. Analogously, for the complement pattern, we must have first a clique, and then an independent set. Consider the two first nodes of an ordering the avoids both patterns. Suppose they are linked by an edge. Then they cannot be both in an independent set, and then in the first partition, the independent set is reduced to one node. (We can always have at least one node in the independent set: if there is none, simply take a node from the clique to be in the independent set.) Thus the rest of the nodes form a clique, and only the last node can be taken in the independent set of the second partition. As a consequence, all the pairs of nodes are linked, except possibly the first and last node. Thus the graph is a 1-split. By complement, if the first nodes are not linked then the graph is an independent set plus possibly one edge, which is also a 1-split. For the other direction, the ordering described above is sufficient. 6. We show that the intersection of the classes of forests and co-forests is trivial (which is enough because of Item 5 in Property 1). A forest has at most n -1 edges, thus the union of the edges in the graph (which is a forest) and in the complement (which is also a forest) is at most 2n -2. Thus n(n -1)/2 ≤ 2n -2, which holds only if n ≤ 4. Thus the class is trivial. 7. Again we show that the intersection is trivial. Consider a bipartite graph with more than two vertices is one of the parts. Its complement necessarily contains a triangle formed by nodes of this part. As a triangle prevents the complement from being bipartite, we know that no part of the original graph has more than two nodes. Thus no graph with more than four nodes belongs to the intersection. 8. Paths are special cases of forests, thus the intersection of paths and co-paths is trivial. 9. Stars are special cases of forests, thus the intersection of stars and co-stars is trivial.

A corollary extracted directly from the proof is the following. Corollary 2. A graph G is a threshold graph if and only if it admits a vertex ordering which is a simplicial elimination scheme for both G and G. Furthermore this vertex ordering yields a transitive orientation of both G and G.

Mirror patterns

We now study to the classes defined by a pattern and its mirror pattern, or its mirrorcomplement pattern. Note that the number of patterns to consider is rather small, because many patterns on three nodes are symmetric. Also note that the mirror of Split is co-Split, thus the associated class has already been considered in Theorem 3. Again see Diagram 5 for illustration. Note that proper interval graphs is an example of a class that can be defined via two different (split-minimal) pairs of forbidden patterns. Also, the patterns Chordal and Interval illustrates the complex interaction that can exists between mirror, complement and mirror-complement patterns.

Proof. We prove the items one by one.

1. An ordering that avoids both patterns is called reversible elimination scheme, and it is known that the graphs that have such orderings are exactly the proper interval graphs [START_REF] Habib | On some simplicial elimination schemes for chordal graphs[END_REF]. 2. As already seen in Lemma 3, this class is the split graphs (by application of the Pattern split rule). 3. This characterization appears in [52].

The intersection of interval and co-interval graphs is included in the classes of split graphs

(as a subclass of chordal and co-chordal graphs). Moreover, the graphs that avoid both patterns have no P 4 (see Figure 6), thus, the class is included in threshold graphs. For the reverse inclusion, consider a threshold graph with the ordering τ = k 1 , . . . k q , i p , . . . i 1 , using notations of Item 11c in Definition 5. Suppose this ordering contains the pattern Interval on three nodes a < b < c. Necessarily a ∈ K and b, c ∈ I (using again the notation of the definition). Then by definition of τ we have b = i α and c = i β with α > β. Now because of the pattern N (i β ) ⊆ N (i α ) which is a contradiction. Similarly τ containing the pattern mirror-co-Interval draws a contradiction with the definition of the ordering. 5. The only vertex orderings of a star graph that satisfies the Star pattern are forced to end with its center. For the mirror pattern we need to start from the center. Therefore only a star graph reduced to one edge can satisfy the two patterns. 6. The intersection of the classes defined by the patterns is trivial, as proved in Theorem 3, thus the class is trivial. 7. Clearly the natural ordering for linear forests avoids these two patterns. Now suppose that a tree that is not a path avoids both patterns. This graph must have a claw (K 1,3 ). But one can easily check that no ordering of a claw can avoid the two patterns. Therefore this class is reduced to paths. 8. The intersection of the classes is trivial, as proved in Theorem 3.

6

Proof of Theorem 2

Program generating the list of classes

In this subsection, we describe and prove the algorithm used for generating all the pattern families of Theorem 2. Note that the task of listing the relevant pattern families could also be carried out by hand, but we think that writing and proving a program produces a more reliable output, reducing the risk of missing a family. Let us first provide some notations and intuition to understand the algorithm that follows. First, we will encode the families of patterns by bit vector of 27 cells (following the numbering of the 27 patterns of Figure 2). (In the algorithm the numbering of the cells starts at 0.) Actually we will start with 8 bits vectors, because we start with only full patterns. Second the algorithm basically consists in generating all the families of full patterns (line 1), then simplifying it by removing equivalent families (lines 2-4), and then we further simplify by using the pattern split rule (lines 6-8). Third, we use the following notations: complement(V ) designates the fact of reversing the vector (the first bit becomes the last bit etc.), and exchange(V ) is the vector V where the bits at position 1 and 4 have been exchanged, as well as the ones at position 3 and 6.

Algorithm 1: Computing split-minimal patterns

Result: A list of patterns 1 D ← all 8-bit vectors except [0,0,0,0,0,0,0,0], 2 for all pairs p, q ∈ D, p = q do 3 if (p = complement(q)) ∨ (p = exchange(q)) ∨ (p = exchange(complement(q))) then List A: (0, 1, 16), (0, 2, 12), (0, 4, 8), [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Bernhart | The book thickness of a graph[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF], [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF]5,[START_REF] Chudnovsky | Berge trigraphs[END_REF], [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Bernhart | The book thickness of a graph[END_REF][START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF], [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF], [START_REF] Bernhart | The book thickness of a graph[END_REF][START_REF] Charbit | A new graph parameter to measure linearity[END_REF][START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF], [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]5,[START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF], [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Corneil | A unified view of graph searching[END_REF], (5,[START_REF] Charbit | A new graph parameter to measure linearity[END_REF][START_REF] Corneil | Vertex ordering characterizations of graphs of bounded asteroidal number[END_REF], [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Charbit | A new graph parameter to measure linearity[END_REF][START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF]. List B: [START_REF] Pok | A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements[END_REF][START_REF] Chudnovsky | Berge trigraphs[END_REF][START_REF] Dirac | On rigid circuit graphs[END_REF], [START_REF] Pok | A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF][START_REF] Damaschke | Forbidden ordered subgraphs[END_REF], [START_REF] Chudnovsky | Berge trigraphs[END_REF][START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF][START_REF] Demange | Partitioning cographs into cliques and stable sets[END_REF], [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF][START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF][START_REF] Duffus | On the computational complexity of ordered subgraph recognition[END_REF], [START_REF] Chvátal | Perfectly orderable graphs[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF], [START_REF] Chvátal | Perfectly orderable graphs[END_REF][START_REF] Corneil | A unified view of graph searching[END_REF][START_REF] Damaschke | Forbidden ordered subgraphs[END_REF], [START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF][START_REF] Corneil | Vertex ordering characterizations of graphs of bounded asteroidal number[END_REF][START_REF] Demange | Partitioning cographs into cliques and stable sets[END_REF], [START_REF] Corneil | A unified view of graph searching[END_REF][START_REF] Corneil | Vertex ordering characterizations of graphs of bounded asteroidal number[END_REF][START_REF] Dusart | A new LBFS-based algorithm for cocomparability graph recognition[END_REF], [START_REF] Corneil | Asteroidal triple-free graphs[END_REF][START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF], [START_REF] Corneil | Asteroidal triple-free graphs[END_REF][START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF][START_REF] Dirac | On rigid circuit graphs[END_REF], [START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF][START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF][START_REF] Duffus | On the computational complexity of ordered subgraph recognition[END_REF], [START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF][START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF][START_REF] Dusart | A new LBFS-based algorithm for cocomparability graph recognition[END_REF]. List C: [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF][START_REF] Demange | Partitioning cographs into cliques and stable sets[END_REF][START_REF] Dushnik | Partially ordered sets[END_REF], [START_REF] Dirac | On rigid circuit graphs[END_REF][START_REF] Duffus | On the computational complexity of ordered subgraph recognition[END_REF][START_REF] Dushnik | Partially ordered sets[END_REF], [START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF][START_REF] Dusart | A new LBFS-based algorithm for cocomparability graph recognition[END_REF][START_REF] Dushnik | Partially ordered sets[END_REF]. We now prove the correctness of the algorithm. Claim 1. All the classes characterized by patterns on three nodes are captured by a family described by a bit vector of D at line 5 (up to complement).

As noted at the end of Subsection 3.5, all the families are equivalent to a family of full patterns. Thus after line 1, D has the property of the claim. Note that we do not consider the trivial family that contains no patterns and corresponds to the all-zero vector. For line 2 to 4, note first that the exchange operation, is the equivalent on vectors of a mirror operation on patterns (because Pattern 1 (resp. 3) is the mirror of Pattern 4 (resp. 6) and that the other full patterns are stable by mirror). Then note that because of our numbering of the patterns in Figure 2, the fact of reversing a vector (on 8 bits) is equivalent of complementing each pattern of the family. Then the removal of line 4 is safe: the only vectors that are removed are the ones that represent a family that has a complement, a mirror or a complement mirror equivalent whose vector stays in D.

Claim 2. All the triplets (a, b, c) listed in Figure 7 are such that the pattern c can be split into a and b by the pattern split rule.

This can be checked triplet by triplet. As stated in Lemma 1, the class defined by a family is stable by the split (or here the reverse split) of a pattern. Thus we still have captured all the families at the end of the algorithm. Also because we apply the simplification with patterns of 0, then 1 and then 2 undecided edges, we saturate the set with the simplification rule, and all the families are split minimal by the end of the algorithm.

Enumeration

Proof strategy and notations. The program described in Subsection 6.1, provides a list of 87 families to investigate in order to have a list of all the classes characterized by a family of patterns on three nodes. The proof of Theorem 2 consists in going through this list and finding the class associated with each family. We use the following notation: [X] i denotes the family composed of the patterns in the list X, described by their numbers from Figure 2; and i is just an index to keep track of the items in the list of 87 families. For example [START_REF] Alon | Finding and counting given length cycles[END_REF]5] 2 is the second family in our list, and it is composed of the patterns 2 and 5, which are respectively Comparability and co-Comparability. Note that for one class, there may be several families, for example through mirror operation; in order to make the comparison with the output of the program easier, we do not change the family to make it "more canonical". For example, the program outputs [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF] and not [START_REF] Brandstädt | Graph Classes: A Survey[END_REF], which means that we consider the pattern mirror-Chordal and not the pattern Chordal.

Isolated nodes and connectivity. In the majority of the classes, additional isolated nodes are allowed. In our orderings they often appear on the left of the other nodes. But some pattern forbid such isolated nodes, except when the graph is reduced to an independent set, in which case we indicate it in parenthesis. Also for some classes, some combination of patterns allow several non-trivial connected component, and some allow only one connected component. Again this is denoted in parenthesis.

Enumeration.

[2] 1 : Comparability graphs. See Theorem 1. Thus we know that the class defined by [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Chudnovsky | Berge trigraphs[END_REF] is contained in the one of [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF] and contains the one of [START_REF] Chudnovsky | Berge trigraphs[END_REF][START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF]. From Theorem 4, we know that [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF] and [START_REF] Chudnovsky | Berge trigraphs[END_REF][START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF] both define proper interval graphs, thus the result.

[13] 8 : Split graphs. See Theorem 1.

[4,13] 9 : Augmented cliques. Let us first give an ordering that avoids the patterns: first the isolated nodes, then the special node, then the nodes of the clique that are neighbor to this node, and then the rest of the clique. It is easy to check that this ordering avoids both patterns. Now, for the reverse direction. Thanks to the proof of Theorem 1 for the split graphs, we know that a graph that avoids Pattern 13 can be divided into first an independent set and then a clique. The pattern 4 forbids that a node of the clique is adjacent to two nodes of the independent set. Thus every node of the clique has at most one neighbor in the independent set, and we claim that this neighbor is the same for every such node. Suppose there is the following scenario in an ordered graph: two nodes x and y from the independent set, and then two nodes u and v from the clique such that (x, u) and (y, v) are edges. One can check that for any ordering of x and y, Pattern 13 appears. This proves the claim. And this finishes the proof: the graph must be a clique, with possibly some nodes linked to one additional node (plus isolated vertices). Therefore, by Item 14c of Definition 5, this class is included in the class of trivially perfect graphs.

For the other direction, we give two proofs. First, as said in Item 14d of Definition 5, a trivially perfect graph is the comparability graph of an arborescence. Let us orient each connected component of this arborescence from the leaves to the root. Consider an ordering given by the following rule: take a source delete it and update the graph. It yields a linear extension of the graph and avoids Pattern 2 (Comparability). This ordering is also a perfect elimination scheme and avoids Pattern 1 (mirror-Chordal). Now a second proof is based on Item 14b in Definition 5: the class of trivially perfect graph, is the class that contains the graph with one node, and is stable by disjoint union and addition of a universal vertex. We build the ordering following this incremental construction: in the the disjoint union we put the different component one after the other, and we add the universal vertices on the right-most position in the ordering. It is easy to check that this construction avoids the patterns. [1,10] 12 : Threshold graphs. Using the Pattern Split rule (Lemma 1), this family is equivalent to [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF]. Syntactically, we deduce that it is included in the class of [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF] 4 , and this family is mirror of Chordal ∪ co-Chordal, which defines threshold graphs (Theorem 3). Also Pattern 1 extends Pattern 9, thus [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF] contains [START_REF] Chudnovsky | Berge trigraphs[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF], which is the mirror of Interval ∪ co-Interval, which also defines threshold graphs (Theorem 3). Thus [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF] defines threshold graphs.

[2,9] 13 : Trivially perfect graphs. As Pattern 1 extends Pattern 9, [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF] 11 extends [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Chudnovsky | Berge trigraphs[END_REF], thus the class is included into trivially perfect graphs. Also, the ordering used for the proof of [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF] 11 avoids the Patterns of [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Chudnovsky | Berge trigraphs[END_REF] thus the result. [9,10] 14 : Threshold graphs. See Theorem 3-4 (along with the mirror property of Item 3 in Property 1). [1,2,4] 15 : Cliques. We claim that no ordering of a P 3 avoids the three patterns. Indeed, if the middle node of the path is respectively first, second or third in the ordering, then the pattern respectively 1, 2 or 4, is present. Thus the class is included in the union of cliques, and any ordering where the cliques appear one after the other avoids the three patterns. [2,4,9] 16 : Cliques. This case is similar to the previous one, [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF] 15 , where 9 replaces 1.

The same ordering works. [2,13] 17 : Threshold graphs. Because of Pattern 13, the class is included into the class of split graph, and using Figure 6, one can check that no ordering of a P 4 avoids both patterns. Thus the class is included into threshold graphs, thanks to Item 11b in Definition 5.

For the other inclusion, using the notations of Item 11c in Definition 5, the ordering i 1 , ..., i p , k q , ...k 1 avoids both patterns. [10,13] 18 : Co-augmented-cliques. Note that the complement-mirror family of [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF] is [START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF], which is extended by [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF] 9 , which characterize augmented cliques. Also note that ordering given in [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF] 9 also avoids Pattern 18. Thus the result. [2,5,13] 19 : Threshold graphs. This class is included into the one of [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF] 17 thus it is included into threshold graphs. For the other inclusion, using again the notations of Item 11c in Definition 5, the ordering i 1 , ..., i p , k q , ...k 1 avoids the three patterns. is well known that co-comparability graphs do not contain induced odd cycles of length ≥ 5 as induced subgraphs [START_REF] Gallai | Transitiv orientierbare graphen[END_REF]. Thus if there is an odd cycle, it is a triangle, and this is forbidden by Pattern 0.

Then the graphs at hand are contained in bipartite cocomparability graphs. Moreover, bipartite graphs are comparability graphs, and comparability co-comparability graphs are permutation graphs. Therefore the class is contained in the class of bipartite permutation graphs. And any cocomparability ordering avoids both patterns, as there is no triangle.

Note that characterizations of bipartite permutation graphs related to orderings are known [START_REF] Spinrad | Bipartite permutation graphs[END_REF], but they are different. [0,3] 27 : Triangle-free ∩ co-chordal. by Fact 2. [0,3,6] 28 : Bipartite chain graph. Patterns 3 and 6 imply that this class is contained into co-proper-interval graphs (thanks to the complement property and Item 3 of Theorem 4).

In addition, it is known that co-interval graphs are comparability graphs of proper interval orders [START_REF] Roberts | Indifference graphs[END_REF]. If in this order, there are three elements x < y < z, then there would be a triangle in the comparability graph, which is forbidden by Pattern 0. Thus the graphs considered are bipartite. Furthermore co-interval graphs do not contain 2K 2 (because intervals do not contain induced C 4 [START_REF] Charbit | A new graph parameter to measure linearity[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 74 defines a trivial class.

[5,6,24] 79 : Stars (without isolated nodes). The inclusion follows from cases [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 80 is trivial.

[7,14,24] 83 : Trivial. As a subclass of case [START_REF] Corneil | A unified view of graph searching[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 82 .

[18,24] 84 : Trivial. Pattern 4 extends Pattern 18, and the class of [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 80 is trivial.

[7,18,24] 85 : Trivial. As a subclass of case of [START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 84 . [6,18,24] 86 : Trivial. As a subclass of case of [START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF][START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] 84 .

[26] 87 : Trivial. See Theorem 1.

Corollary of the proof

From the proof we can extract the following results. These results follow respectively from the cases [5,[START_REF] Corneil | Asteroidal triple-free graphs[END_REF] 43 , [START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF][START_REF] Chvátal | Perfectly orderable graphs[END_REF] 35 , [0, 5] 26 , [5,[START_REF] Chvátal | Perfectly orderable graphs[END_REF] 33 , [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF] 11 , [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Chudnovsky | Berge trigraphs[END_REF] 13 , [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Chudnovsky | The strong perfect graph theorem[END_REF] 12 , [START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF] 17 of the proof above.

Algorithmic aspects

We now consider the algorithmic implications of Theorem 2. From a complexity point of view, we first note that for any pattern family (on any number of nodes), given the ordering it is possible to check in polynomial time if all the patterns are avoided. This means that the ordering is a polynomial certificate that a graph is in a class characterized by patterns, and thus the recognition of any such class is a problem in NP.

For the case of patterns on three nodes, we first show that graph searches are especially well-suited for recognition of the classes, and then give a more exhaustive result about the complexity of the problem.

Recognition via graph searches

The ordering in which the nodes are visited during various graph searches has been studied in the literature, and is characterized using the so-called 4 points conditions on 3 vertices [START_REF] Corneil | A unified view of graph searching[END_REF]. Such searches are essential tools for recognition of well-structured graph classes. Therefore it is interesting to see how far we can go with graph searches to recognize the classes listed in Theorem 2. To our knowledge here is the state of the art in this direction. Proof. Chordal. If G is a chordal graph, any LBFS provides a simplicial elimination ordering, i.e. an ordering avoiding the characteristic pattern of chordal graphs [61]. Trivially perfect graphs. As shown in [START_REF] Pok | A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements[END_REF] one LBFS is enough to recognize and certify trivially perfect graphs. Furthermore it produces a characteristic vertex ordering. Linear forest. For each connected component just apply a BFS starting in a vertex x and ending at y, then apply a second BFS starting at y. If G is a path, clearly the second BFS ordering avoids the forbidden pattern. Forest. We have already observed in Theorem 1, that if G is a tree any generic search ordering provides an ordering avoiding the characteristic pattern. Star. Perform a BFS starting at a vertex x and ending at y. Let x 0 the unique neighbour of y (if y has more neighbours then G is not a star). If G is a star, any ordering of the vertices finishing with x 0 avoids the forbidden pattern. Caterpillars. Let us now consider a caterpillar C, using a result in [START_REF] Charbit | A new graph parameter to measure linearity[END_REF] 2 consecutives BFS, the second one starting at the end vertex of the first one, provide on a caterpillar an ordering avoiding the forbidden patterns. But they also provide a diametral path, since it has been proved that for trees it yields a diametral path [START_REF] Handler | Minimax location of a facility in an undirected tree graph[END_REF]. 2-star. Same as for caterpillars with an extra test on the length of the diametral path that must be exactly 3. Bipartite. Let us apply any Layered search on G, for example a BFS. Starting from x 0 the layers are L 1 , . . . L k . Consider the ordering τ = x 0 , L 2 , . . . L 2p , L 1 , . . . L 2p+1 when k = 2p + 1. Clearly if G is bipartite τ avoids the forbidden pattern. Proper interval. If G is a proper interval graph, a series of 3 consecutive LBFS + always produces an ordering avoiding the characteristic first 2 patterns of Theorem 1 of proper interval graph [START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF]. Interval. If G is an interval graph, a series of 5 consecutive LBFS + followed by a special LBFS * always produces and ordering avoiding the characteristic pattern of interval graphs [START_REF] Corneil | The LBFS structure and recognition of interval graphs[END_REF]. It should also be noticed that a similar result can be obtained using another graph search, namely Maximal Neighbourhood Search, see [51]. Split. Compute a maximal clique tree via a LBFS on G (as explained in [START_REF] Galinier | Chordal graphs and their clique graphs[END_REF]) and identify the clique of maximal size C. Do the same procedure on G (without building G just using G) and identify I the clique of maximum size in G. If C and I partition V (G) then G is a split graph. So with 2 LBFS we can construct an ordering that avoids the forbidden pattern. Threshold graphs. A maximal degree search (MDS) which is a generic graph search that starts at a vertex of maximal degree and then break ties with the degrees, i.e., at each step the selected vertex is eligible and has a maximum degree in the remaining graph.

If the graph G is a threshold graph, this search generates an ordering τ of the vertices as described in Corollary 2. Let x 0 the first vertex in τ . To check if G is a threshold graph it suffices to check if N (x 0 ) is a clique and N (x 0 ) an independent set and that the neighbourhoods N (x 0 ) of are totally ordered with respect to their τ ordering. All of this can be done in linear time. Triangle-free. Any ordering works, so we can use any graph search. Triangle-free ∩ co-chordal. A LBFS applied in the complement of the graph will provide an ordering of the vertices avoiding the 2 patterns. Co-comparability. If G is a co-comparability graph, a series of n consecutive LBFS + always produces an ordering avoiding the characteristic pattern of cocomparability graphs [START_REF] Dusart | A new LBFS-based algorithm for cocomparability graph recognition[END_REF]. Permutation. In [START_REF] Corneil | On the power of graph searching for cocomparability graphs[END_REF] a permutation recognition algorithm is presented which works as follows. First compute a cocomp ordering τ for G and a cocomp ordering σ for G. Then transitively orient G (resp. G) using σ(resp. using τ ). Then use a depth first search to compute the two orderings that represent the permutation graph, both of them avoids the patterns. Using the above result for cocomparability graphs, thus in this case an ordering avoiding the patterns can be obtained via 2n + 2 consecutive graph searches. Permutation Bipartite graphs. Add to the recognition of permutation graphs a BFS to check if the graph is bipartite.

Therefore for each of the classes of Theorem 2, we can produce the characteristic ordering via a series of graph searches. Then using a brute force algorithm we can check if this ordering avoids the patterns in O(n 3 ). Within this complexity we can also recognize complement classes.

Complexity results

As a consequence using Theorems 2 and 5 we can recover the result of [START_REF] Hell | Ordering without forbidden patterns[END_REF]. Theorem 2 actually allows us to get the following more fine-grain result. Theorem 6. All classes defined with sets of patterns on 3 vertices and their complements can be recognized in linear time, except triangle-free and comparability graphs.

Proof. Of course some of the classes of graphs in Theorem 2 such as stars, 2-stars, cliques, 1-splits, augmented cliques and complete bipartite graphs are quasi-trivial and therefore they are linear-time recognizable.

As detailed in Theorem 5 the "classic" classes of graphs such as bipartite graphs, forests, linear forests, caterpillars, chordal graphs, interval graphs, proper interval graphs, split graphs, permutation graphs can be recognized in linear time via a graph search (for example LexBFS). Therefore their complement classes can also be recognized in linear time, using the usual technique of partition refinement. Similar results also hold for trivially perfect graphs graphs [START_REF] Pok | A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements[END_REF] or threshold graphs and bipartite chain graphs and their complement [START_REF] Heggernes | Linear-time certifying recognition algorithms and forbidden induced subgraphs[END_REF].

The co-triangle-free ∩ chordal graph class can also be recognizable in linear time in the following way. First check if the graph is chordal and then compute its maximum independent set and check whether it has strictly more than 2 vertices. Both operations can be done in linear time see [61]. Similarly for their complement.

Their exists a linear time for the recognition of permutation graphs [START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF]. This algorithm produces two comparability orderings for the graph itself and its complement. It also gives a permutation representation of the graph which can be also tested in linear time. Then it suffices to check for the bipartitness, which can also be done in linear time. Similarly co-bipartitness can be checked in linear time and therefore complement can be also recognized in linear time.

Let us now discuss what is known about the complexity of the recognition of the two remaining classes and their complement. For these classes the problem is not the computation of a good ordering but its certification. Up to our knowledge, no graph search can produce an ordering and its certification in linear time.

Let ω be the best exponent of the complexity of an algorithm for n × n boolean matrix multiplication. Using algorithm in [START_REF] Vassilevska | Multiplying matrices faster than coppersmith-winograd[END_REF] ω = 2, 3727.

First, triangle-free graphs (resp. co-triangle-free) can be recognized in O(m 1.41 ) (resp. O(m 1.186 )) for sparse graphs and in O(n 2,3727 ) for dense ones. Indeed, the best known algorithm [START_REF] Alon | Finding and counting given length cycles[END_REF] for recognition of triangle-free graphs is in O(m 2ω ω+1 ) = O(m 1.41 ) if ω = 2, 3727. For dense graphs one may use boolean matrix multiplication in O(n 2,3727 ).

Recognition of triangle-free graphs is still an active area of research and nowadays some lower bounds under complexity hypothesis are discussed see [START_REF] Vassilevska | Subcubic equivalences between path, matrix, and triangle problems[END_REF].

For the recognition of co-triangle-free graphs using a similar technique, it can be done in O(m 1.186 ) [START_REF] Durand | Complexity issues for the sandwich homogeneous set problem[END_REF] for sparse graphs and using matrix multiplication for denses graphs.

1 2 ω ) = O(m
Second for comparability graphs, unfortunately the recognition algorithm LexBFS based presented in Theorem 5 has a worst-case complexity of O(n • m).Similalry for comparability graphs a vertex ordering that avoids its pattern if it is a comparability graph can be computed in linear time [START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF], but it is still not known if one can check if this ordering avoids the comparability pattern in linear time.

But comparability graphs and their complement classes can be recognized in O(n 2,3727 ) using matrix multiplication.

The best known algorithm is in O(m 2ω ω+1 ) = O(m 1.41 ) [START_REF] Habib | On 2 subquadratic algorithms for transitive closure and reduction[END_REF]. For dense graphs one can also use matrix multiplication. For dense cocomparability graphs up to our knowledge only the matrix multiplication has been proposed so far.

Corollary 5. All classes of graphs defined with sets of patterns on 3 vertices can be recognized in O(n 2,3727 ).

Discussions and open problems

In this section, we discuss related topics, such as larger patterns, and review some open problems.

Larger patterns

In this paper we have focused on patterns on three nodes, and we have now good picture the the associated classes. An obvious next step is to look at larger patterns. We review a few topics in this direction.

Straight line patterns and colorings

To illustrate the expressivity of the pattern characterizations, we show here how to express colorability notions in terms of forbidden patterns.

Let us define a notion of a colorability and a type of patterns. First, a graph is (a, b)colorable [START_REF] Demange | Partitioning cographs into cliques and stable sets[END_REF], if one can partition the vertices into a independent sets and b cliques. In particular, classic k-colorability corresponds to (k, 0)-colorability. Second, a straight line pattern is a pattern where the decided edges are exactly the ones between consecutive vertices. For example, on three nodes, Bipartite and Split are straight line patterns, because they are formed of an edge followed by respectively another edges and a non-edge, with the top edge being undecided. Also, on two nodes, the two patterns with an edge and a non-edge are straight line patterns. As noted in Subsection 3.1, these define the independent sets and the cliques.

Note that on the four examples above there is a link between colorability and straight line patterns: the bipartite graphs, split graphs, independent sets and cliques are respectively the (2,0), (1,1), (1,0) and (0,1)-colorable graphs. This is actually a general phenomenon, as stated in the following theorem. Before proving this theorem, let us highlight a remarkable property: the ordering of the edges and non-edges in the pattern does not matter. In other words, two straight line patterns with the same number of edges and non-edges define the exact same class.

Proof. We prove the result by induction on a + b. For a + b ≤ 2, we have already mentioned that the property is true (the case of (0, 2) follows from (2, 0) by symmetry). Now, let P be an arbitrary straight line pattern with a edges and b non-edges, with a + b > 2. It is sufficient to prove the result for the case when two last nodes of P are linked by an edge. Indeed, if it is a non-edge, then we can consider the complement, and the result follows. Let P be the same as P , but without the last vertex (and thus without the last edge). By induction, we assume that P satisfies the property.

We first show that the graphs of C P are (a, b)-colorable. Consider an ordered graph G = (V, E) that avoids P . Let X be the set of vertices of G that have no neighbor to the right in the ordering. Note that X is an independent set. We claim that the ordered subgraph G of G induced by V \ X avoids P . Indeed, if there is an occurrence of P in this subgraph then there is an occurrence of P in G. This is because the last vertex of the occurrence has a neighbor on its right, and the pattern finishes by an edge. Then as G avoids P , by induction it is (a -1, b)-colorable. The fact that X is an independent sets, leads to G being (a, b)-colorable.

Conversely, let G = (V, E) be (a, b)-colorable. Consider an independent set X of the (a, b)-coloring. Let G be the subgraph of G induced by V \ X. This subgraph is (a -1, b)colorable. Thus by induction, it has an ordering that avoids P . Now, consider the ordering of G, made by concatenating this ordering of G and the nodes of X. This ordering avoids P . Indeed an occurrence of P would imply an occurrence of P in the part of the ordering corresponding to G .

In the case b = 0, Theorem 7 corresponds to the classical Mirsky's Theorem, that states that the chromatic number of a graph G is the minimum over all acyclic orientations of G of the maximum length of a directed path [START_REF] Mirsky | A dual of Dilworth's decomposition theorem[END_REF].

Corollary 6 (Mirsky's Theorem). A graph G is k-colorable if and only if there exists an order on its vertices that avoids the straight line pattern with k edges. described in Figure 6. For cographs, there actually exists a more compact characterization using 2 patterns of size 3 and one of the P 4 orderings [START_REF] Damaschke | Forbidden ordered subgraphs[END_REF]. Other classes related to orderings of P 4 have been studied, like the perfectly orderable graphs [START_REF] Chvátal | Perfectly orderable graphs[END_REF], see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF].

Intersection graphs There is one more specific class with a pattern on four nodes that we are aware of. This is the class of p-box graphs [START_REF] Soto | p-Box: A new graph model[END_REF], also known under other names in [START_REF] Cardinal | Intersection graphs of rays and grounded segments[END_REF] and [START_REF] José | Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity[END_REF]. Roughly, a graph is p-box if it is the intersection graph of rectangles having a corner on a line. These are characterized by the pattern of Figure 11 1 2 3 4

Figure 11 The pattern that characterizes p-Box graphs.

Note that this pattern is an extension of the pattern for outerplanar graphs, and therefore the p-box graphs contain the outerplanar graphs. More generally a geometric approach is fruitful when looking at the extensions of the outerplanar pattern [START_REF] Feuilloley | Graph classes defined by forbidden patterns: a geometric approach[END_REF].

Graph parameters based on patterns

For each pattern P , it is possible to define a graph parameter, that we call P -number. One could also define the F-number for a family F. Consider an ordered graph whose edges are colored. We say that the coloring avoids the pattern, if for each color, the ordered graph induced by the edges of this color avoids the pattern. The P -number of a graph is the minimum number k such that there exists an ordering of the graph and a coloring of its edges into k colors, such that the coloring avoids the pattern P .

The P -number has already been considered in the literature for some specific patterns P . For example, when P is the pattern of outerplanar graphs (Figure 9), the P -number is known as the book thickness [START_REF] Bernhart | The book thickness of a graph[END_REF] or stack-number [START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF]. Also for the pattern of Figure 10, the parameter is the queue number [START_REF] Heath | Laying out graphs using queues[END_REF].

Finally, if one fixes a number k of colors, one can use the number of occurrences of the pattern as another parameter. For the pattern of Figure 9, this is the k-page book crossing number [START_REF] Shahrokhi | The book crossing number of a graph[END_REF].

One can view our main result as follows: Recognition of graph having F-number equal to 1, is polynomial (mostly linear) for every family of patterns on 3 vertices. Therefore a natural question is: What is the complexity of recognizing F-number equal to 2, for the same families ?

Ordering as a distributed certificate

As noted in Section 7, the recognition of the classes defined by patterns is always a problem in NP, as a correct ordering is a certificate that can be checked in polynomial time. This is notable, as it means that for all these classes there is a 'standard' certificate.

Certification mechanisms also appears in distributed computing. Namely in distributed decision [START_REF] Feuilloley | Introduction to local certification[END_REF][START_REF] Feuilloley | Survey of ditributed decision[END_REF], one aims at deciding locally whether the network has some property. This often requires to help the nodes by giving them some piece of global information, that can be checked locally. This takes the form of a label for each node. It has been noted that when the problem is to decide whether the network belongs to a class defined by a pattern (for example that the network is acyclic), providing each node with its rank in ordering is the optimal way to certify the property [START_REF] Feuilloley | Local certification in distributed computing: error-sensitivity, uniformity, redundancy, and interactivity[END_REF].

Structural questions

There are several interesting questions about the relations between classes defined by patterns. For example, what can be said about the intersection of two classes defined by patterns? The example of interval ∩ permutation shows that having two classes corresponding to patterns on three nodes does not imply that the intersection can be described by patterns on three nodes. On a related note, we emphasized in the text that in many cases the union-intersection property holds, but not always. It would be interesting to understand more precisely in which case it does. Another question is about pattern extension. When a patten is strictly included into another one, is it the case that the classes are also strictly included? It is the case when we restrict our attention to some specific pattern shapes [START_REF] Feuilloley | Graph classes defined by forbidden patterns: a geometric approach[END_REF], but we have no general proof. Also note that when considering families, it is not true that adding a pattern reduces the family defined, as many cases Section 6 illustrate.

  Closure) If for every pattern P of the family, N (P ) = ∅, then the class is closed under edge deletion. 3. (Mirror) The family mirror-F defines the same graph class as F, that is, C mirror-F = C F . 4. (Exchange-Complement) The class C co-F defines the complement class of C F . 5. (Union) Given two families F 1 and F 2 , C F1∪F2 ⊆ C F1 ∩ C F2 . 6. (Extension) If a family F 2 extends a family F 1 then C F1 ⊆ C F2 .

Figure 2

 2 Figure 2The 27 patterns on three nodes. By convention since mirror-Split=co-Split, we will ignore the pattern mirror-Split.

Figure 3

 3 Figure 3 Partial inclusion diagram of the classes that appear in Theorem 2. More refined diagrams can be found in Figures 4, 5.

Figure 4

 4 Figure 4 Refinement of Figure 3 in which we represent the cases where P = P1&P2 and the union-intersection property holds by a label & link to P1 and P2 above, and P below.

Figure 5

 5 Figure 5Representation of the non-trivial characterizations of Theorems 3 and 4. The edges labeled with "co" mean: the family made by taking the pattern on the top endpoint and its complement characterize the class below. The edges labeled with "mi" mean the same but with mirror instead of complement. And "co-mi" designate both operations. The + means that the edge has both labels.

Lemma 3 . 5 . 6 .

 356 The following equalities hold: 1. Forest = Chordal & Triangle-Free, and furthermore forests = chordal ∩ triangle-free. 2. Bipartite = Comparability & Triangle-Free, and furthermore bipartite = triangle-free ∩ comparability. 3. Split = mirror-Chordal & co-Chordal, and furthermore split=chordal ∩ co-chordal [33, 42]. 4. Interval = Chordal & co-Comparability, and furthermore interval = chordal ∩ co-comparability [37]. Linear Forest = Interval & mirror-Forest = Forest & mirror-Interval. Star = Bipartite & Split = mirror-Forest & co-Interval.

Property 2 . 1 . 2 . 3 .

 2123 The following equalities hold. The cycle-free interval graphs are the caterpillars. The bipartite split graphs are the 2-stars. The cycle-free co-interval graphs are the 2-stars.

Theorem 3 . 7 . 8 . 9 .

 3789 The following characterizations hold: 1. Triangle-Free ∪ co-Triangle-Free defines a trivial class. 2. Comparability ∪ co-Comparability defines the permutation graphs. 3. Chordal ∪ co-Chordal defines the threshold graphs. 4. Interval ∪ co-Interval defines the threshold graphs. 5. Split ∪ co-Split defines the 1-split. 6. Forest ∪ co-Forest defines a trivial class. Bipartite ∪ co-Bipartite defines a trivial class. Linear Forest ∪ co-Linear Forest defines a trivial class. Star ∪ co-Star defines a trivial class. Diagram 5 illustrates the non-trivial characterizations of Theorem 3 (and of Theorem 4).

Figure 6

 6 Figure 6The 12 different orderings of a P4.

Theorem 4 . 1 . 2 . 3 . 4 . 5 . 6 .

 4123456 The following characterizations hold: Chordal ∪ mirror-Chordal defines the proper interval graphs. Chordal ∪ mirror-co-Chordal defines the split graphs. Interval ∪ mirror-Interval defines the proper interval graphs. Interval ∪ mirror-co-Interval defines the threshold graphs. Star ∪ mirror-Star defines a trivial class. Star ∪ mirror-co-Star defines a trivial class. 7. Forest ∪ mirror-Forest defines paths. 8. Forest ∪ mirror-co-Forest defines a trivial class.

4 Remove q from D 5 7 for

 457 Append 19 zeros after each bit vector in D {% to upgrade them as 27-bit vectors}, 6 for all p ∈ D do every triplet (a, b, c) of Lists A, B, C in Figure 7 do 8 if the a th and the b th bit of p are 1s then transform them into 0s, and make the c th bit of p a 1. 9 Return D.

Figure 7

 7 Figure 7 Lists of triplets describing the pattern split rule.

[ 2 , 5 ] 2 : 1 ] 3 : 1 , 6 ] 4 : 9 ] 5 :

 2521316495 Permutation graphs. See Theorem 3. [Chordal graphs. See Theorem 1, in addition to the mirror property (Item 3 in Property 1). [Threshold graphs. The mirror property (Item 3 in Property 1) implies that this family is equivalent to [4,3], that is Chordal and co-Chordal. Then the result follows from Theorem 3. [Interval graphs. See Theorem 1 (and mirror property). [1,4] 6 : Proper interval graphs. See Theorem 4.

[ 4 , 9 ] 7 :

 497 Proper interval graphs. We can note that Pattern 1 extends Pattern 9, and Pattern 4 extends Pattern 18.

1 , 2 ] 11 :

 1211 [START_REF] Corneil | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs[END_REF][START_REF] Corneil | A unified view of graph searching[END_REF] 10 : 1-Split. See Theorem 3. [Trivially perfect graphs. Thanks to Figures 6 and 8, one can check that no ordering of C 4 or P 4 can avoid both patterns.

Figure 8

 8 Figure 8The three different orderings of a C4.

[ 2 , 4 , 13 ] 20 :

 241320 Connected cliques. Similarly to the case of[START_REF] Dujmovića | Stacks, queues and tracks: layouts of graph subdivisions[END_REF][START_REF] Alon | Finding and counting given length cycles[END_REF][START_REF] Brandstädt | Graph Classes: A Survey[END_REF] 15 , the patterns forbid an induced P 3 , thus every connected component is a clique. If there are two component with one or more edges, then Pattern 13 appears, thus the graphs of the class are composed of one clique, plus possibly isolated vertices. In the other direction, having the isolated vertices first, and then the clique avoids the pattern. [4,10,13] 21 : Connected cliques (without isolated nodes or of size < 3). As Pattern 2 extends Pattern 10, the class of [4,10,13] is included into the one of [2, 4, 13] 20 , that is in the connected cliques. Moreover, if there is an isolated node, it cannot be on the left or on right of an edge because of respectively Pattern 10 and 13. As a consequence, isolated nodes can appear only if the clique has strictly less than three nodes. An ordering avoiding the patterns has first the possible isolated nodes and then the clique. [2,13,18] 22 : Connected cliques. As Pattern 4 extends Pattern 18, the class of [2,13,18] is included into the one of [2, 4, 13] 20 , that is in the connected cliques. And the same ordering works. [10,13,18] 23 : Connected cliques. As Pattern 2 extends Pattern 10, the class is included in the class of [2, 13, 18] 22 , that is in the connected cliques. And the same ordering works. [0] 24 : Triangle-free graphs. See Theorem 1. [0,7] 25 : Trivial. See Theorem 3 [0,5] 26 : Bipartite permutation. First we show that the graphs of the class are bipartite. It

[ 6 ,

 6 [START_REF] Lekkeikerker | Representation of a finite graph by a set of intervals on the real line[END_REF]), thus these graphs are included into bipartite chain graphs (by Item 15c ofDefinition 5). Now consider a bipartite chain graph, and the notations of Item 15a of Definition 5. The vertex ordering a 1 , . . . , a |A| , b 1 , . . . , b |B| avoids the three patterns. [0,3,5] 29 : Complete bipartite graphs. The class is contained into the class of [0, 5] 26 , that is in the class of bipartite permutation graphs. Also because of Pattern 3, we know that there is at most one connected component that is not an isolated node (otherwise the right-most vertex, and two vertices of another non-trivial component would make it appear). If the non-trivial component is not a complete bipartite graph, then the following situation should appear: two nodes a, b on one side, two nodes c, d, on the other side, (b, c) not being an edge (because the bipartite graph is not complete), (a, c) and (b, d) being edges (to insure the connectivity), and (a, d) being arbitrary. Now note that because of Patterns 3 and 5, if a node has two non-neighbors that are linked by an edge, then this node should appear before the two other nodes. This means that b is before a and c, and c is before b and d which is a contradiction. Thus the completeness of the bipartite graph. The ordering with isolated nodes and then one class after the other avoids the three patterns. [0,3,5,6] 30 : Complete bipartite graphs (without isolated nodes). As a subclass of case [0, 3, 5] 29 , it is included into complete bipartite graphs, and the patterns 3, 5 and 6, forbid isolated nodes respectively, on the right, middle and left of an edge. For the other direction, the same ordering as for Pattern 6 works (without the isolated nodes). [12] 31 : Bipartite graphs. See Theorem 1. [7,12] 32 : Trivial class. co-Triangle-Free & Bipartite defines a trivial class, since such a graph can have at most 4 vertices. [5,12] 33 : Bipartite permutation graphs. By the pattern split rule, this class is equivalent to the one of [0, 2, 5]. Remember that [2, 5] 2 characterizes permutation graphs (by Item 2 of Theorem 3) and that Pattern 12 characterizes bipartite graphs (Theorem 1), thus the class is included into bipartite permutation graphs. For the other inclusion, the ordering given for Item 2 of Theorem 3 avoids Pattern 2 and 5, and it also avoids Pattern 0, as the graph is bipartite. [12,15] 34 : Trivial class. See Theorem 3. [3,12] 35 : Bipartite chain graphs. The class contains only bipartite graphs because of Pattern 12. A graph of the class cannot contain a 2K 2 , as the right-most node of a 2K 2 in the ordering would form Pattern 3 with the nodes of the other edge. Thus the class is included in bipartite chain graph by Item 15c of Definition 5. As for [0, 3, 6] 28 , the vertex ordering with first the isolated nodes and then a 1 , . . . , a |A| , b 1 , . . . , b |B| (with the notations of Item 15a of Definition 5) avoids the patterns . 24] 75 : Stars. Included in stars, because of Pattern 24. The ordering with the leaves, then the isolated nodes and then the center avoids the patterns. [19,24] 76 : Trivial. Pattern 16 extends Pattern 24, and [16, 19] 42 defines a trivial class. [5,24] 77 : Stars. Included in stars, because of Pattern 24. The ordering with the isolated nodes, the leaves and the center avoids both patterns. [15,24] 78 : Trivial. Pattern 7 extends Pattern 15, and

  75 and from the fact that the patterns forbid isolated nodes. Having the center at the end is enough to avoid the patterns. [4,24] 80 : Trivial. Since Pattern 24 forces that only the last node can be the right-hand of an edge, and then Pattern 4 prevents this node to have more than one neighbor. [4,7,24] 81 : Trivial. As Pattern 16 extends Pattern 24, and the class of [7, 16] 40 is trivial. [14,24] 82 : Trivial. Pattern 4 extends Pattern 14, and the class of

Corollary 3 . 1 . 2 . 3 . 4 . 5 .

 312345 The following characterizations hold: Caterpillars can be defined via Forest & co-Comparability. Bipartite chain graphs via co-Chordal & Bipartite. Bipartite permutation graphs via Triangle-Free & co-Comparability or via Bipartite & co-Comparability. Trivially perfect graphs via Chordal & Comparability or via Interval & Comparability. Threshold graphs via Chordal & co-Interval or via Comparability & Split

Theorem 5 .

 5 Generic search and BFS, DFS, LBFS, MNS and Maximal Degree Search (MDS) can be used to obtain very simple algorithms for the recognition of the graph classes cited in Theorem 2.

Corollary 4 .

 4 ([47]) All classes defined with sets of patterns on 3 vertices can be recognized in O(n 3 ).

Theorem 7 .

 7 If P is a straight line pattern with a edges and b non-edges, then the class C P is the class of (a, b)-colorable graphs.

12. A proper interval graph is

	equivalently ([60]):
	a. the intersection graphs of a set of intervals, where no interval is included in another.
	b. a unit interval graph , that is interval graphs where all the intervals of the geometric
	representations have the same length.
	c. an indifference graph, that is a graph where every node v can be given a real number
	k v such that (u, v) ∈ E if and only if |k u -k v | ≤ 1.
	13. A caterpillar graph is equivalently:
	a. A forest where each tree has a dominating path.
	b. A (T 2 , cycle)-free graph, where T 2 is the graph on seven nodes obtained by taking a
	3-star, and appending an additional node on each leaf.

14.

A trivially perfect graph is equivalently (

[38,[START_REF] Wolk | The comparability graph of a tree[END_REF]

):

& & & &

A generalization of this result appears in section 8.

Note that it is perhaps more common to consider the reverse ordering, but this is equivalent, as we will see in Section 3.

Acknowledgements:

We wish to thank the website graphclasses.org [27], and its associated book [4] that helped us to navigate through the jungle of graph classes. Furthermore the authors wish to thank Yacine Boufkad, Pierre Charbit and Flavia Bonomo for fruitful discussions on this subject. The first author is thankful to José Correa, Flavio Guinez and Mauricio Soto, for the very first discussions on this topic back in 2013. Finally, we thanks the reviewers for their thorough reading and their helpful comments.

, Inria GANG

Complexity of recognition for larger patterns

The previous paragraph has an important consequence: unlike patterns on three nodes, patterns on four nodes can define classes that are NP-hard to recognize. Indeed the straight line pattern with three edges defines the class of 3-colorable graphs, and 3-colorability is an NP-hard property [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

On the other hand, it is not true that all patterns on four nodes define a class that is NP-hard to recognize. For example, outerplanar graphs can be recognized in linear time [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF], and are defined by the pattern on four nodes of Figure 9. Figure 9 The pattern that characterizes outerplanar graphs.

Finally, to illustrate the difficulty of having an intuition of the complexity of recognition, based only on the shape of the pattern, let us mention one more class. Graphs of queue number 1 [START_REF] Heath | Laying out graphs using queues[END_REF], are the that avoid the pattern of Figure 10. These graphs are NP-hard to recognize [45], although the pattern is just a shuffling of the pattern of outerplanar graphs. Figure 10 The pattern that characterizes graphs of queue number 1.

Understanding the P/NP dichotomy for arbitrary patterns is clearly an essential problem here. In this direction, Duffus et al [START_REF] Duffus | On the computational complexity of ordered subgraph recognition[END_REF] conjectured that most classes characterized by a 2-connected pattern are NP-complete to recognize.

Patterns on four nodes

Before tackling arbitrary patterns, it seems reasonable to gather knowledge about patterns on four nodes. We already mentioned a few patterns on four nodes, for which we know the associated class. Unfortunately, we do not know much more, although there are 3 6 = 729 such patterns.

From patterns on three nodes Some patterns on four nodes are directly related to patterns on three nodes. For a pattern Q on three nodes, one can consider the pattern P on four nodes, made by adding a node on the right-end with only undecided edges to the nodes of Q. Then the class C P is exactly the set of graphs that can be formed by taking a graph of C Q and (possibly) adding a vertex with an arbitrary adjacency. This follows from a proof similar to the one of Theorem 7.

From forbidden subgraph characterizations Another way to reuse things we know is to exploit the remark at the end Subsection 3.3: a forbidden induced subgraph characterization can always be turned into a forbidden pattern characterization by taking all the orderings of this subgraph. For example, the cographs as introduced in [START_REF] Seinsche | On a property of a class of n-colorable graphs[END_REF] are the P 4 -free graphs, thus they are exactly the graphs that admit an ordering of the vertices avoiding the 12 patterns