Jaroslav Nešetřil
email: nesetril@iuuk.mff.cuni.cz

Patrice Ossona De Mendez

Roman Rabinovich
email: roman.rabinovich@tu-berlin.de

Sebastian Siebertz
email: siebertz@uni-bremen.de

Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋆

A R T I C L E I N F O

A B S T R A C T Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following. 1) The number of unlabeled graphs of order with linear rank-width at most is at most (2 + 1)( + 1)! 2 ( 2 ) 3 +1 2) Graphs with linear rankwidth at most are linearly -bounded. Actually, they have bounded -chromatic number, meaning that they can be colored with ( ) colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family F of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in F .

From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most are first-order transductions of linear orders. This result could also be derived from Colcombet's theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth.

Introduction

A primary concern in many areas of mathematics is to classify structures (or classes of structures) according to their intrinsic complexity. In this paper we consider three approaches and their interplay to the notion of structural complexity: the model theoretic approach based on the standard dividing lines that are stability and dependence, the algebraic approach founding the notion of rankwidth and linear rankwidth, and a more classical graph theoretical approach based on colorings and decompositions of graphs.

A theory of sparse structures was initiated in [START_REF] Nešetřil | Sparsity (Graphs, Structures, and Algorithms)[END_REF], which mainly fits to the classification of monotone classes (i.e., classes that are closed under taking subgraphs). The theory has led to the nowhere dense/somewhere dense dichotomy that can be observed in several areas of graph theory, theoretical computer science, model theory, analysis, category theory and probability theory. Motivated by the connection with model theory -nowhere dense classes are monadically stable [START_REF] Adler | Interpreting nowhere dense graph classes as a classical notion of model theory[END_REF] and even have low VC-density [START_REF] Pilipczuk | On the number of types in sparse graphs[END_REF] -and by a possible extension of first-order model-checking algorithms for bounded expansion classes [START_REF] Dvořák | Deciding first-order properties for sparse graphs[END_REF][START_REF] Dvořák | Testing first-order properties for subclasses of sparse graphs[END_REF] and for nowhere dense classes [START_REF] Grohe | Deciding first-order properties of nowhere dense graphs[END_REF], these notions were extended to classes that are obtained as first-order transductions of sparse classes, the structurally sparse classes [START_REF] Nešetřil | Structural sparsity[END_REF][START_REF] Gajarský | First-order interpretations of bounded expansion classes[END_REF]. The central tool used in our approach is the transduction machinery, which establishes a fruitful bridge between graph theory and finite model theory. Informally, a first-order transduction is a way to interpret a structure in another structure, where the new structure is defined by means of first-order formulas with set parameters. Indeed, a standard approach of both model theory and computability theory is to determine the relative complexity of two structures by showing that the first interprets in the second, and is therefore not more complex than the second. In this context, important classes of structures are the class of finite linear orders and the class of element to finite set membership graphs (powerset graphs), as they define the two most important model theoretical dividing lines: stability, which corresponds to the impossibility to interpret arbitrarily large linear orders, and dependence (or NIP, for "Non-Independence Property"), which corresponds to the the impossibility to interpret arbitrarily large membership graphs. The versions of these properties where we allow set parameters are monadic stability and monadic dependence.

The use of first-order transductions naturally fits the study of hereditary classes (i.e., classes that are closed under taking induced subgraphs). If we consider classes that are obtained as first-order transductions of other classes, the natural tractability limit is the realm of monadically NIP structures, as non monadically NIP classes allow to interpret the whole class of finite graphs. In this world, typical well behaved monadically NIP but monadically unstable classes of graphs are classes with bounded rankwidth (like cographs) and classes with bounded linear rankwidth (like halfgraphs). This justifies a specific study of these classes, as well as the classes that admit finite -covers with bounded rankwidth [START_REF] Kwon | Graph-theoretic concepts in computer science[END_REF] or classes that admit finite -covers with bounded linear rankwidth (like unit interval graphs), as they naturally extend structurally bounded expansion classes, which admit finite -covers with bounded shrubdepth [START_REF] Gajarský | First-order interpretations of bounded expansion classes[END_REF]. However we do not know whether classes with such covers are monadically NIP. The whole framework is schematically pictured in Figure 1.

This paper consists of two parts. The first part sets the scene and builds the framework that supports our study. The second part roots our study in concrete problems. In particular, we consider classes with bounded linear rankwidth and show how model theoretic and structural properties of classes with bounded linear rankwidth allow to prove new properties of these classes. In particular we prove the following theorems (formal definitions will be given in Section 2). Theorem 4.6. Let C be a class of graphs with bounded linear rankwidth. Then the following are equivalent: From the graph theoretic point of view, we briefly discuss how classes with bounded rankwidth differ from classes with bounded linear rankwidth and give some lower bounds for -boundedness of graphs with bounded rankwidth and for graphs with bounded linear rankwidth. Then we prove upper bounds for graphs with bounded linear rankwidth. Theorem 5.17. Let ( ) = 2(2 + 1)( + 1)! 2 ( +12 ) . The -chromatic number of every graph (that is the minimum order of a partition of ( ) where each part induces a cograph) is bounded by (lrw( )), where lrw( ) denotes the linear rank-width of . Hence ( ) ≤ (lrw( )) ( ).

Theorem 4.6 and a weaker form of Theorem 5.17 (Theorem 4.3) are proved in Section 4 by using the notion of linear NLC-width expression and Simon's factorization forest theorem.

The strong form of Theorem 5.17 is proved in Section 5 by a fine analysis of linear rankwidth decompositions. Along the way we also obtain an upper bound for the number of graphs with linear rankwidth at most . Theorem 5.15. Unlabeled graphs with linear rankwidth at most can be encoded using at most 2 + log 2 + log 2 (12∕ ) + (log 2 ) bits per vertex. Precisely, the number of unlabelled graphs of order with linear rankwidth at most is at most

(2 + 1)( + 1)! 2 ( 2 ) 3 +1
.

Classes with low complexity

Structures and logic

A signature Σ is a finite set of relation and function symbols, each with a prescribed arity. In this paper we consider only signatures with relation symbols. A Σ-structure consists of a finite universe (or domain) ( ) and interpretations of the symbols in the signature: each relation symbol ∈ Σ, say of arity , is interpreted as a -ary relation ⊆ ( ) . For a signature Σ, we consider standard first-order logic over Σ. If is a structure and ⊆ ( ) then we denote by [ ] the substructure of induced by . The Gaifman graph of a structure is the graph with vertex set ( ) where two distinct elements , ∈ are adjacent if and only if and appear together in some tuple in some relation of . For a formula ( 1 , … , ) with free variables and a structure , we define

( ) = {( 1 , … , ) ∈ ( ) ∶ ⊧ ( 1 , … , )}.
We usually write ̄ for a tuple ( 1 , … , ) of variables and leave it to the context to determine the length of the tuple. The above equality then rewrites as

( ) = { ̄ ∈ ( ) | ̄ | ∶ ⊧ ( ̄ )}. Also, for a formula ( ̄ , ̄ ) and ̄ ∈ ( ) | ̄ | we define ( ̄ , ) = { ̄ ∈ ( ) | ̄ | ∶ ⊧ ( ̄ , ̄ )}.
For signatures Σ, Σ + with Σ ⊂ Σ + , the Σ-reduct of a Σ + -structure is the structure obtained from by "forgetting" the relations in Σ + ⧵ Σ. For a signature Σ, a monadic lift of a Σ-structure is a Σ + -structure Λ( ) such that Σ + is the union of Σ and a set of unary relation symbols and is the Σ-reduct of Λ( ). Note that in the case of graphs, a monadic lift corresponds to a coloring of the vertices.

Graphs, colored graphs and trees.

Graphs can be viewed as finite structures over the signature consisting of a binary relation symbol , interpreted as the edge relation, in the usual way. For graphs we follow the notations of [START_REF] Nešetřil | Sparsity (Graphs, Structures, and Algorithms)[END_REF]. In particular, for a graph we denote by | | the order of , that is the number of vertices of , and by ‖ ‖ the size of , that is the number of edges of . A graph is a subgraph of , denoted ⊆ if can be obtained from by deleting some vertices and edges. For a subset of vertices of a graph we denote by [ ] the subgraph of induced by , that is the subgraph of with vertex set and same adjacencies as in and we say that a graph is an induced subgraph of if it is isomorphic to some [ ]. We write ⊆ if is an induced subgraph of . A class of graphs C is monotone if every subgraph of a graph in C also belongs to C ; it is hereditary if every induced subgraph of a graph in C also belongs to C .

For a non-negative integer , a ≤ -subdivision of a graph is a graph obtained from by subdividing each of its edges by at most vertices (not necessarily the same number on each edge). An -subdivision of is a ≤ -subdivision of where each edge is subdivided by exactly vertices.

For a finite label set Γ, by a Γ-colored graph we mean a graph enriched by a unary predicate for each ∈ Γ. A rooted forest is an acyclic graph together with a unary predicate ⊆ ( ) selecting one root in each connected component of . A tree is a connected forest. The depth of a node in a rooted forest is the number of vertices in the unique path between and the root of the connected component of in . In particular, is a root of if and only if has depth 1 in . The depth of a forest is the largest depth of any of its nodes. The least common ancestor of nodes and in a rooted tree is the common ancestor of and that has the largest depth.

Sparse graph classes

Treewidth, pathwidth and treedepth. Treewidth is an important width parameter of graphs that was introduced in [START_REF] Robertson | Graph minors II. Algorithmic aspects of tree-width[END_REF] as part of the graph minors project. Pathwidth is a more restricted width measure that was introduced in [START_REF] Robertson | Graph minors I. Excluding a forest[END_REF]. The notion of treedepth was introduced in [START_REF] Nešetřil | Tree depth, subgraph coloring and homomorphism bounds[END_REF].

For our purposes it will be convenient to define these width measures in terms of intersection graphs. Let 1 , … , be a family of sets. The intersection graph defined by this family is the graph with vertex set { 1 , … , } and edge set {{ , } ∶ ∩ ≠ ∅}. A chordal graph is the intersection graph of a family of subtrees of a tree. An interval graph is the intersection graph of a family of intervals. A trivially perfect graph is the intersection graph of a family of nested intervals. Alternatively, a trivially perfect graph is the comparability graph of a bounded-depth tree order.

The treewidth of a graph is one less than the minimum clique number ( ) of a chordal supergraph of [START_REF] Robertson | Graph minors II. Algorithmic aspects of tree-width[END_REF], the pathwidth of a graph is one less than the minimum clique number of an interval supergraph of [START_REF] Bodlaender | A partial -arboretum of graphs with bounded treewidth[END_REF], and the treedepth of a graph is the minimum clique number of a trivially perfect supergraph of (direct from the definition): A class C of graphs has bounded treewidth, bounded pathwidth, or bounded treedepth, respectively, if there is a bound ∈ ℕ such that every graph in C has treewidth, pathwidth, or treedepth, respectively, at most . Classes with bounded expansion. A graph is a depth-topological minor of a graph if contains a subgraph isomorphic to a ≤ 2 -subdivision of . A class C of graphs has bounded expansion if there is a function ∶ ℕ → ℕ such that ‖ ‖ | | ≤ ( ) for every ∈ ℕ and every depth-topological minor of a graph from C . Examples of classes with bounded expansion include the class of planar graphs, any class of graphs with bounded maximum degree, or more generally, any class of graphs that excludes a fixed topological minor. We lift the notion with bounded expansion to classes of structures over an arbitrary fixed signature, by requiring that their class of Gaifman graphs has bounded expansion. In particular, a class of colored graphs has bounded expansion if and only if the class of underlying uncolored graphs has bounded expansion. For an in-depth study of classes with bounded expansion we refer the reader to the monograph [START_REF] Nešetřil | Sparsity (Graphs, Structures, and Algorithms)[END_REF].

Nowhere dense classes.

A class C is nowhere dense if there is a function ∶ ℕ → ℕ such that ( ) ≤ ( ) for every ∈ ℕ and every depth-topological minor of a graph from C [START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF][START_REF] Nešetřil | On nowhere dense graphs[END_REF].

Monadic stability, monadic dependence, and low VC-density

The model theoretic approach of complexity is based on the study of properties rather than on the study of objects. This is witnessed by the fact that the central subjects of study in model theory are theories and that the actual structures are only considered as models of theories. Nevertheless, most notions defined on theories have their counterpart on models or on classes of models. One of the main goals of stability theory (also known as classification theory) is to classify the models of a given first-order theory according to some simple system of cardinal invariants. In this respect, elementary theories are stable theories and still reasonably well behaved theories are NIP theories (also called dependent theories). These notions can be translated to classes of structures as follows: Definition 2.1. A class C of structures is stable if for every first-order formula ( ̄ , ̄ ) there exists an integer such that for every structure ∈ C and for all tuples

̄ 1 , … , ̄ , ̄ 1 , … , ̄ of elements of , if ⊧ ( ̄ , ̄ ) ⟺ ≤ (1)
for all , ∈ [ ], then ≤ .

The graph on vertices 1 , … , , 1 , … with edges { , } for 1 ≤ ≤ ≤ is called a half-graph or ladder of length , see Figure 2.

Definition 2.2.

A class C of structures is dependent (or NIP) if for every first-order formula ( ̄ , ̄ ) there exists an integer such that for every structure ∈ C and for all tuples

̄ ( ∈ [ ]) and, ̄ ( ⊆ [ ]) of elements of , if ⊧ ( ̄ , ̄ ) ⟺ ∈ (2)
for all ∈ [ ] and all ⊆ [ ], then ≤ .

Note that every stable class is dependent.

A stronger notion of stability and of dependence arises when one allows to apply arbitrary monadic lifts to the structures in C before using the formula . These variants are called monadic stability and monadic dependence. The expressive power gained by the monadic lift is so strong that tuples of free variables can be replaced by single free variables in the above definitions [START_REF] Baldwin | Second-order quantifiers and the complexity of theories[END_REF].

Definition 2.3.

A class C of Σ-structures is monadically stable if for every expansion Σ + of Σ by unary predicate symbols and every first-order Σ + -formula ( , ) there exists an integer such that for every monadic lift + of any structure ∈ C and for all elements 1 , … , , 1 , … , of , if

+ ⊧ ( , ) ⟺ < (3)
for all , ∈ [ ], then ≤ .

Definition 2.4.

A class C of Σ-structures is monadically dependent (or monadically NIP) if for every expansion Σ + of Σ by unary predicate symbols and every first-order Σ + -formula ( , ) there exists an integer such that for every monadic lift + of any structure ∈ C and for all elements ( ∈ [ ]) and ( ⊆ [ ]) of , if

+ ⊧ ( , ) ⟺ ∈ (4)
for all ∈ [ ] and all ⊆ [ ], then ≤ .

Note that every monadically stable class is monadically dependent. For a formula ( ̄ , ̄ ), the VC-density vc C ( ) of a formula in a class C (containing arbitrarily large structures) is defined as

vc C ( ) = lim →∞ sup ∈C sup ⊆ ( ) | |= log |{ ( ̄ , ) ∩ | ̄ | ∶ ̄ ∈ ( ) | ̄ | }| log | | The VC-density vc C of the class C is vc C ( ) = sup{vc C ( ) ∶ ( ̄ ; ̄ ) is a formula with | ̄ | = }.
According to the Sauer-Shelah Lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem; stability and order for models and theories in infinitary languages[END_REF], a class C is NIP if and only if vc C ( ) < ∞ for every formula . However, it is possible for a NIP class (and even for a stable class) to have vc C (1) = ∞. On the other hand, it is easily checked that (unless structures in C have bounded size) for every positive integer we have vc C ( ) ≥ . A class C has low VC-density if vc C ( ) = for all integers [START_REF] Guingona | On VC-minimal theories and variants[END_REF]. In particular, if a class C has low VC-density we have vc C ( ) < ∞ for every formula thus C is NIP. We say that C has monadically low VC-density if the class { + ∶ + monadic lift of ∈ C } has low VC-density. Note that every class with monadically low VC-density is monadically NIP. Theorem 2.5. Let C be a class of graphs.

1. If C is nowhere dense, then C is monadically stable ([Adler, Adler [START_REF] Adler | Interpreting nowhere dense graph classes as a classical notion of model theory[END_REF]; Podewski, Ziegler [START_REF] Podewski | Stable graphs[END_REF]).

If C is nowhere dense, then C has monadicallly low VC-density (Pilipczuk, Siebertz, and Toruńczyk [42]]).

Theorem 2.6 ([Adler, Adler [START_REF] Adler | Interpreting nowhere dense graph classes as a classical notion of model theory[END_REF]; Podewski, Ziegler [START_REF] Podewski | Stable graphs[END_REF]). Let C be a monotone class of graphs. If C is NIP, then C is nowhere dense.

Interpretations and transductions

In this paper, by an interpretation of Σ ′ -structures in Σ-structures we mean a transformation defined by means of formulas ( ̄ ) (for each ∈ Σ ′ of arity | ̄ |) and a formula ( ). For every Σ-structure , the Σ ′ -structure ( ) has domain ( ) and the interpretation of each relation ∈ Σ ′ is given by ( ) = ( ) ∩ ( ) | ̄ | . For some fixed interpretation we often say that a structure is an interpretation of (it would be more precise to say that is an interpretation in ) if = ( ).

A transduction is the composition •Λ of a monadic lift Λ and an interpretation . It is easily checked that the composition of two transductions is again a transduction. Again, for some fixed transduction we often say that a structure is a transduction of if = ( ).

Let C and D be classes of Σ C -structures and Σ D -structures, respectively. Let be an interpretation of Σ D -structures in Σ + C -structures, where The definitions of interpretations and transductions given above naturally extend to any logic . We speak of an -interpretation if the formulas and in the above definition are -formulas, and of an -transduction if we combine a monadic lift with an -interpretation. If the logic  is not mentioned explicitly, we mean first-order logic FO. Another commonly considered logic is monadic second-order logic (MSO).

Σ + C ⧵ Σ C is
We want to emphasize that in this paper our focus is not the study of what graph class D is produced by a transduction from a class C , it is rather the study of how to encode D in C . In particular when we say that a class D is a transduction of a class C , we do not need to use all the graphs in C , nor to verify properties of the monadic lifts. For example, when D is a transduction of C , then every subclass of D is also a transduction of C .

The definition of monadic stability and monadic dependence can naturally be given in terms of transductions. Let H denote the class of half-graphs, that is the class of the bipartite graphs with vertex set { 1 , … , , 1 , … , } and edges { , } for every 1 ≤ ≤ ≤ (see Figure 2). Let G denote the class of all finite graphs. We have

C is monadically stable ⟺ C ∕ / / / / H . C is monadically NIP ⟺ C ∕ / / / / G .

Lemma 2.7 ([3]). A stable class C is monadically unstable if and only if C has a transduction to the class of all

1-subdivisions of complete bipartite graphs.

In particular, if a stable class is not monadically stable it is not monadically NIP as there is an easy transduction from the class of all 1-subdivisions of complete bipartite graphs to the class of all finite graphs. As monadically stable classes are monadically NIP we deduce the following corollary.

Corollary 2.2. A class C is monadically stable if and only if it is both stable and monadically NIP.

We use the term of structurally xxx for classes that are transductions of classes that are xxx. For instance, a class has structurally bounded treewidth if it is the transduction of a class with bounded treewidth.

The following characterizations of classes with bounded treewidth, pathwidth, rankwidth, linear rankwidth, and shrubdepth show the deep connections between these width measures and logical transductions (and at this point will serve as a definition of the notions of rankwidth, linear rankwidth and shrubdepth).

1. A class C of graphs has bounded treewidth (pathwidth, respectively) if and only if there exists an MSOtransduction such that the incidence graph of every ∈ C is the result of applying to some tree (path, respectively) ( [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF] (see also [START_REF] Courcelle | Graph structure and monadic second-order logic: a language-theoretic approach[END_REF], Theorem 7.47)).

2. A class C of graphs has bounded rankwidth (linear rankwidth, respectively) if and only if there exists an MSOtransduction such that every ∈ C is the result of applying to some tree (path, respectively). ( [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF] (see also [START_REF] Courcelle | Graph structure and monadic second-order logic: a language-theoretic approach[END_REF], Theorem 7.47)).

3. A class C of graphs has bounded rankwidth (linear rankwidth, respectively) if and only if there exists an FOtransduction such that every ∈ C is the result of applying to some tree order (linear order, respectively) ( [START_REF] Colcombet | A combinatorial theorem for trees[END_REF]).

4. A class C of graphs has bounded shrubdepth if and only if there exist an FO-transduction and a height ℎ such that every ∈ C is the result of applying to some tree of depth at most ℎ ( [START_REF] Ganian | When trees grow low: Shrubs and fast MSO 1[END_REF][START_REF] Ganian | Shrub-depth: Capturing height of dense graphs[END_REF]).

We can rewrite properties (3) and ( 4) as follows:

C has bounded rankwidth ⟺ Y ≤ / / / / C , C has bounded linear rankwidth ⟺ L ≤ / / / / C , C has bounded shrubdepth ⟺ ∃ Y / / / / C ,
where Y ≤ denotes the class of all finite tree orders, L ≤ denotes the class of all linear orders, and Y denotes the class of trees with depth at most . Note that in the characterizations above Y ≤ can be replaced by the class of trivially perfect graphs (or by the larger class of cographs) and L ≤ can be replaced by the class of transitive tournaments or by the class of half-graphs.

Remark 2.8. Since the class of all graphs does not have bounded rankwidth, we deduce that if C has bounded rankwidth we have C ∕ / / / / G . Hence every class with bounded rankwidth is monadically NIP.

In particular, Corollary 2.2 implies the following: Remark 2.9. A class with bounded rankwidth is monadically stable if and only if it is stable.

Weakly sparse classes

It appears that a basic property that makes a graph class dense is that graphs in it contain arbitrarily large complete bipartite graphs , with partitions of equal size (bicliques). Indeed, forbidding a biclique as a subgraph (or, equivalently, forbidding a clique and a biclique as induced subgraphs) is known to have a strong consequence on classes with low complexity. We call a class C weakly sparse if it excludes some biclique , as a subgraph. Theorem 2.10. Let C be a weakly sparse class of graphs.

1. If C has bounded shrubdepth, then C has bounded treedepth [START_REF] Gajarský | First-order interpretations of bounded expansion classes[END_REF]. [START_REF] Gurski | The Tree-Width of Clique-Width Bounded Graphs without[END_REF]. [START_REF] Gurski | The Tree-Width of Clique-Width Bounded Graphs without[END_REF].

If C has bounded linear rankwidth, then C has bounded pathwidth

If C has bounded rankwidth, then C has bounded treewidth

We call a class sparsifiable if it is transduction-equivalent to a weakly sparse class.

The assumption that a class is weakly sparse allows frequently to work with induced subgraph instead of subgraphs. For instance: Theorem 2.11 (Dvořák [15]). Let C be a hereditary weakly sparse graph class. Then Conversely, assume towards a contradiction that the class C is weakly sparse and not nowhere dense. According to Theorem 2.11 we can find arbitrarily large induced -subdivisions of complete graphs for some integer . It is then easy to interpret (in a monadic lift) arbitrary graphs, contradicting the hypothesis that C is monadically NIP.

Corollary 2.4. Every sparsifiable monadically NIP class of graphs is structurally nowhere dense.

Decompositions and covers

For ∈ ℕ, a -cover of a structure is a family  of subsets of ( ) such that every set of at most elements of is contained in some

∈  . If C is a class of structures, then a -cover of C is a family  = ( ) ∈C , where  is a -cover of . A 1-cover is simply called a cover. A -cover  is finite if sup{| | ∶ ∈ C } is finite. Let C [ ] denote the class structures { [ ] ∶ ∈ C , ∈  }. For a class W we say that a cover  is a W -cover if C [ ] ⊆ W . If W is
a class of bounded treedepth, bounded shrubdepth, etc., we call a W -cover a bounded treedepth cover, bounded shrubdepth cover, etc. The class C admits low treedepth covers, low shrubdepth covers, etc. if and only if for every ∈ ℕ there is a finite -cover  of C with bounded treedepth, shrubdepth, etc.

Theorem 2.12 ([36, 19]). A class of graphs has bounded expansion if and only if it has low treedepth covers.

The following notion of shrubdepth has been proposed in [START_REF] Ganian | When trees grow low: Shrubs and fast MSO 1[END_REF] as a dense analogue of treedepth. Originally, shrubdepth was defined using the notion of tree-models. We present an equivalent definition based on the notion of connection models, introduced in [START_REF] Ganian | When trees grow low: Shrubs and fast MSO 1[END_REF] under the name of -partite cographs with bounded depth.

A connection model with labels from Γ is a rooted labeled tree where each leaf is labeled by a label ( ) ∈ Γ, and each non-leaf node is labeled by a binary relation ( ) ⊂ Γ × Γ. If ( ) is symmetric for all non-leaf nodes , then such a model defines a graph on the leaves of , in which two distinct leaves and are connected by an edge if and only if ( ( ), ( )) ∈ ( ), where is the least common ancestor of and . We say that is a connection model of the resulting graph . A class of graphs C has bounded shrubdepth if there are a number ℎ ∈ ℕ and a finite set of labels Γ such that every graph ∈ C has a connection model of depth at most ℎ using labels from Γ.

A cograph is a graph that has a connection model (called a cotree) with a labels set Γ containing only a single label. Cographs are perfect graphs, that is, graphs in which the chromatic number of every induced subgraph equals the clique number of that subgraph.

Theorem 2.13 ([19]). A class of graphs has structurally bounded expansion if and only if it has low shrubdepth covers.

Lemma 2.14 ([19]). Every class that admits 2-covers of bounded shrubdepth is sparsifiable.

-boundedness

Recall that a class of graphs C is -bounded if there exists a function ∶ ℕ → ℕ such that for every graph in C we have ( ) ≤ ( ( )) [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]. If is polynomial (resp. linear) then the class is said to be polynomially -bounded (resp. linearly -bounded). A prototypical example of -bounded class is the class of perfect graphs, which is the class of graphs , such that all induced subgraphs of have their chromatic number equal to their clique number.

The c-chromatic number of a graph is the minimum size of a partition 1 , … , of the vertex set of such that [ ] is a cograph for each ∈ {1, … , } [START_REF] Gimbel | Partitions of graphs into cographs[END_REF]. We denote by ( ) the c-chromatic number of . As cographs are perfect [START_REF] Berge | Strongly perfect graphs[END_REF] we have the following general inequality for every graph : Proof. Let ℎ ∈ ℕ and let Γ be a finite set such that every graph ∈ C has a connection model of depth at most ℎ using labels from Γ, and let ∈ Γ. It is easily checked that the subgraph of induced by the vertices with label has a connection model using only the label . It follows that this induced subgraph is a cograph, hence the c-chromatic number of is at most |Γ|.

( ) ≤ ( ) ( ).

Corollary 2.5. Every class C that admits 1-covers of bounded shrubdepth has bounded c-chromatic number, and hence is linearly -bounded.

Proof. Indeed, if C admits a 1-cover of bounded shrubdepth then C has bounded c-chromatic number, thus is linearly -bounded.

Rankwidth and linear rankwidth

We now turn to the study of classes of bounded rankwidth and linear rankwidth. After recalling several equivalent definitions of these width measures, we prove that for every proper hereditary family F of graphs (like cographs), there is a class C with bounded rankwidth such that for every integer there is a graph ∈ C such that all vertex colorings with colors contain a monochromatic induced subgraph not in F .

Definitions

Classes with bounded rankwidth and classes with bounded linear rankwidth enjoy several characterizations. In particular, for a class C the following are equivalent:

1. C has bounded rankwidth, Cliquewidth and linear cliquewidth. Graphs of bounded treewidth have bounded average degree and therefore the application of treewidth is (mostly) limited to sparse graph classes. Cliquewidth was introduced in [START_REF] Courcelle | Handle-rewriting hypergraph grammars[END_REF] with the aim to extend hierarchical decompositions also to dense graphs. However, there is no known polynomial-time algorithm to determine whether the cliquewidth of an input graph is at most for fixed ≥ 4. A notable application of cliquewidth is the extension of Courcelle's Theorem for testing MSO properties in cubic time (or linear time if a clique decomposition is given) on graph classes of bounded cliquewidth [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF]. The notion of linear cliquewidth has been introduced in [START_REF] Gurski | On the relationship between NLC-width and linear NLC-width[END_REF]. We denote by cw( ) the cliquewidth of a graph and by lcw( ) the linear cliquewidth of .

NLC-width and linear NCL-width. The notions of NLC-width and linear NLC-width were introduced in [49] and [START_REF] Gurski | On the relationship between NLC-width and linear NLC-width[END_REF]. Before giving the definition of linear NLC-width we recall some terminology of formal language theory. An alphabet is a finite set Ω, whose members are called letters (or symbols). A word (or string) of length over the alphabet Ω is a sequence of letters from Ω, and we denote by Ω * (resp. Ω + ) the set of all words (resp. of all non-empty words) over Ω.

Definition 3.1. For ∈ ℕ, let be a finite set, and let Ω ( ) be the alphabet whose letters are quadruples ( , , , ), where

• ∈ , • ∈ [ ],
• ⊆ [ ], and

• ∶ [ ] → [ ].
For a letter = ( , , , ) ∈ Ω ( ) we write , , and for , , and , respectively.

Let be a positive integer. We say that a word ∈ Ω ( ) + is admissible if no two letters and of have the same -value. We denote by ( ) the set of all admissible words in Ω + .

Definition 3.2. A linear NLC-expression of width over is a word in ( ).

With linear NLC-expressions of width over we recursively associate a colored graph Ξ( ) whose vertices are the -values of the letters of , colored by colors from [ ] as follows.

• If | | = 1, then Ξ( ) is the single vertex graph, with vertex colored .

• If = ′ , where | | = 1, then Ξ( ) is the graph obtained from Ξ( ′ ) by adding the vertex with color , connecting to all vertices of Ξ( ′ ) that have a color in , and finally, changing the color of each vertex with color to color ( ).

The linear NLC-width of a graph is the minimum integer such that is identical to the graph Ξ( ) for some ∈ ( ( )).

It is clear that the vertex set of Ξ( ) can be identified with the letters of . and that for every subword of the graph Ξ( ) is the subgraph of Ξ( ) induced by the -values of the letters of .

We have [START_REF] Gurski | On the relationship between NLC-width and linear NLC-width[END_REF]: linear NLC-width( ) ≤ lcw( ) ≤ linear NLC-width( ) + 1.

(5)

Neighborhood-width. The neighborhood-width of a graph is the smallest integer , such that there is a linear order 1 , … , on the vertex set of such that for every vertex the vertices with ≤ can be divided into at most subsets, each members having the same neighborhood with respect to the vertices with > . The neighbourhoodwidth of a graph differs from its linear clique-width or linear NLC-width at most by one [START_REF] Gurski | Linear layouts measuring neighbourhoods in graphs[END_REF].

Rankwidth and linear rankwidth. The notion of rankwidth was introduced in [START_REF] Oum | Approximating clique-width and branch-width[END_REF] as an efficient approximation to cliquewidth. For a graph and a subset ⊆ ( ) we define the cut-rank of in , denoted ( ), as the rank of the | | × | ( ) ⧵ | 0-1 matrix over the binary field 2 , where the entry of on the -th row and -th column is 1 if and only if the -th vertex in is adjacent to the -th vertex in ( ) ⧵ . If = ∅ or = ( ), then we define ( ) to be zero.

A subcubic tree is a tree where every node has degree 1 or 3. A rank decomposition of a graph is a pair ( , ), where is a subcubic tree with at least two nodes and is a bijection from ( ) to the set of leaves of . For an edge ∈ ( ), the connected components ofinduce a partition ( , ) of the set of leaves of . The width of an edge of ( , ) is ( -1 ( )). The width of ( , ) is the maximum width over all edges of (and at least 0). The rankwidth rw( ) of is the minimum width over all rank decompositions of . When the graph has at most one vertex then there is no rank decomposition and the rankwidth is defined to be 0.

Cliquewidth and rankwidth are functionally related [START_REF] Oum | Approximating clique-width and branch-width[END_REF]: For every graph we have

rw( ) ≤ cw( ) ≤ 2 rw( )+1 -1. (6)
Hence, a class C of graphs has bounded cliquewidth if and only if C has bounded rankwidth.

The linear rankwidth of a graph is a linearized variant of rankwidth, similarly as pathwidth is a linearized variant of treewidth. Let be an -vertex graph and let 1 , … , be an order of ( ). The width of this order is max 1≤ ≤ -1 ({ 1 , … , }). The linear rankwidth of , denoted lrw( ), is the minimum width over all linear orders of . If has less than 2 vertices we define the linear rankwidth of to be zero. An alternative way to define the linear rankwidth is to define a linear rank decomposition ( , ) to be a rank decomposition such that is a caterpillar and then define linear rankwidth as the minimum width over all linear rank decompositions. Recall that a caterpillar is a tree in which all the vertices are within distance 1 of a central path.

It was proved in [START_REF] Gurski | Linear layouts measuring neighbourhoods in graphs[END_REF] that the linear cliquewidth and the linear rankwidth of a graph are bound to each other: Precisely, for every graph we have lrw( ) ≤ linear NLC-width( ) ≤ lcw( ) ≤ 2 lrw( ) .

(

A linear ordering witnessing lrw( ) ≤ (or deciding lrw( ) > ) for fixed can be computed in time ( 3 ) [START_REF] Jeong | The "art of trellis decoding" is fixed-parameter tractable[END_REF].

Lexicographic product

We denote by • the lexicographic product of and , that is the graph with vertex set ( ) × ( ) where ( , ) is adjacent to ( ′ , ′ ) is is adjacent to ′ in or = ′ and is adjacent to ′ in . Note that this operation, though non-commutative, is associative. By ⊕ we denote the operation of forming the disjoint union of and and connecting all vertices of the copy of to all vertices of the copy of .

Lemma 3.3. For all graphs , we have rw(( • ) ⊕ 1 ) = max(rw( ⊕ 1 ), rw( ⊕ 1 )).

Proof. Let ( , ) and ( , ) be rank decompositions of ⊕ 1 and ⊕ 1 , respectively, of minimum width. Assume the leaves of are ( ) ∪ { } and the leaves of are ( ) ∪ { }. Consider | | copies of and glue these copies on by identifying each leaf of that is a vertex of with the vertex of the associated copy. The obtained tree together with the naturally inherited mapping from the vertices of ( • ) ⊕ 1 to the leaves of is a rank decomposition of ( • ) ⊕ 1 (see Figure 4). Now consider any edge of this rank decomposition of ( • ) ⊕ 1 . There are two cases:

• Assume the edge is within the rank decomposition of ⊕ 1 . Let , be the induced partition of the vertices of ( • ) ⊕ 1 . This partition corresponds to a partition ′ , ′ of ⊕ 1 . Let ∶ → ′ be the natural projection. We may assume that the vertex belongs to in ( • ) ⊕ 1 (hence to ′ in ⊕ 1 ). For every vertex ∈ we have

( • )⊕ 1 ( ) ∩ = ( ⊕ 1 ( ( )) ∩ ′ ) × ( ). Hence the cut-rank of in ( • ) ⊕ 1 equals the cut-rank of ′ in ⊕ 1 .
• Otherwise, the edge is within the rank decomposition of a copy of ⊕ 1 . Let , be the induced partition of the vertices of ( • ) ⊕ 1 , where ⊆ { 0 } × ′ for some 0 ∈ ( ) and some ′ ⊆ ( ). Then all vertices ∈ ({ 0 }× ( ))⧵ have the neighborhood ({ 0 }× ( ))∩ on , while the vertices ∈ ⧵({ 0 }× ( )) have the same neighborhood in , which is

{ 0 } × ⊕ 1 ( ). It follows that the cut-rank of in ( • ) ⊕ 1 equals the cut-rank of ′ in ⊕ 1 .
It follows that rw(( • ) ⊕ 1 ) ≤ max(rw( ⊕ 1 ), rw( ⊕ 1 )). The reverse inequality follows from the fact that ⊕ 1 and ⊕ 1 are both induced subgraphs of (

• ) ⊕ 1 . G ⊕ K 1 H ⊕ K 1 (G • H) ⊕ K 1
(Indeed, ⊕ 1 ⊆

• if contains at least one edge.) We remark that a stronger version of Corollary 3.1 holds for cliquewidth (the cliquewidth does not increase when going to the closure under lexicographic product), which follows from Lemma 3.4 of [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF].

By substituting each vertex of ( ) in the linear order witnessing lrw( ) by the linear order of ( ) witnessing lrw( ) we similarly obtain the following results. Lemma 3.5. For all graphs , we have lrw( • ) ≤ lrw( ) + lrw( ).

Proof. Let < 1 be a linear order of ( ) witnessing lrw( ) and let < 2 be a linear order of ( ) witnessing lrw( ). Let < be the lexicographic order on = ( ) × ( ) defined by < 1 , < 2 , i.e., ( , ) < ( ′ , ′ ) if < ′ or ( = ′ and < ′ ). Let = ( , ) ∈ and let ( , ) ≤ . We have

• (( , )) ∩ > = ( ( ) ∩ ( ) > ) × ( ) ∪ { } × ( ( ) ∩ ( ) > ) .
It follows that the vector space spanned by the sets • (( , )) ∩ > is in the sum of the vector space spanned by the sets ( ( ) ∩ ( ) > ) × ( ) (which has dimension at most lrw( )) and of the vector space spanned by the sets { } × ( ( ) ∩ ( ) > ) (which has dimension at most lrw( )). Hence the claim follows.

Ramsey properties of rankwidth

In this section we prove that the class of all graphs with rankwidth at most + 1 is "Ramsey" for the class of all graphs with rankwidth at most , in the following sense.

Theorem 3.6. For all integers , and every graph with rankwidth at most there exists a graph ′ = • with rankwidth + 1 and with the property that every -coloring of ′ contains an induced monochromatic copy of .

Proof. We define inductively graphs • for ≥ 1: •1 = and, for ≥ 1 we let

•( +1) = • • = • • . According to Corollary 3.1 we have rw({ • ∶ ∈ ℕ}) ≤ + 1.
We prove by induction on that in every -partition of ′ = • one class induces a subgraph with a copy of . If = 1 the result is straightforward. Let > 1. Consider a partition 1 , … , of the vertex set of • . If all the copies of •( -1) forming • contain a vertex in , then • [ ] contains an induced copy of . Otherwise, there is a copy of •( -1) in • whose vertex set is covered by 1 , … , -1 . By induction hypothesis •( -1) [ ] contains an induced copy of for some . Corollary 3.2. Let F be a proper hereditary class of graphs. Then there exists a class C with bounded rankwidth such that for every integer there is ∈ C with the property that for every partition of ( ) into classes, one class induces a graph not in F .

Corollary 3.3. The class of graphs with rankwidth at most 2 does not have the property that its graphs can be vertex partitioned into a bounded number of cographs, the class of graphs with rankwidth at most 3 does not have the property that its graphs can be vertex partitioned into a bounded number of circle graphs, etc.

Proof. This follows from Theorem 3.6 by noticing that rw( 4 ) = 1 (where 4 denotes the path on 4 vertices) and 4 is a forbidden induced subgraph for cographs , and that rw( 5 ) = 2 (where 5 = 5 ⊕ 1 denotes the wheel on 6 vertices) and 5 is not a circle graph.

Lower bounds for -boundedness

Dvořák and Kráľ [START_REF] Dvořák | Classes of graphs with small rank decompositions are -bounded[END_REF] proved that classes with bounded rankwidth are -bounded. This result has been strengthened by Bonamy and Pilipczuk [START_REF] Bonamy | Graphs of bounded cliquewidth are polynomially -bounded[END_REF] who proved that classes with bounded rankwidth are polynomially -bounded. We give here a lower bound on the degrees of the involved polynomials. We write ( ) for the fractional chromatic number of a graph , which is defined as

( ) = inf ( • ) ∶ ∈ ℕ .
Theorem 3.7. For ∈ ℕ, let be a polynomial such that for every graph with rankwidth at most we have ( ) ≤ ( ( )). Then deg ∈ Ω(log ).

Proof. As shown in [START_REF] Geller | The chromatic number and other functions of the lexicographic product[END_REF] for all graphs and we have ( • ) = ( • ( ) ). Furthermore we have ( • ( ) ) ≥ ( ) ( ). We deduce that ( • ) ≥ ( ) ( ). Hence for every integer we have ( • ) ≥ ( ) . As For a sufficiently large integer there exists a triangle-free graph of order with ( ) ≥ 1 9 √ log (see [START_REF] Kim | The Ramsey number (3, ) has order of magnitude 2 ∕ log[END_REF]). As the rankwidth of a graph of order is at most

⌈ ∕3⌉ we have > rw( ⊕ 1 ) thus deg ≥ 1 2 log 2 -(1) log .
Linear rankwidth. We give a short proof in Section 4 (Corollary 4.1) that classes with bounded linear rankwidth are linearly -bounded using the equivalence between classes with bounded linear rankwidth and classes with bounded linear NLC-width. We improve the obtained upper bound of the ∕ ratio in Section 5 using a more technical analysis of linear rank-width (Theorem 5.17), leading to an order of magnitude of 2 ( 2 ) . We now prove that the ratio ∕ can be as large as for some constant > 1 and for graphs with arbitrarily large linear rankwidth and clique number . From Lemma 3.5 we deduce lrw( • 5 ) ≤ 2 . As ( • 5 ) = 2 and as ( • 5 ) ≥ ( 5 ) ( 5 ) -1 = 3(5∕2) -1 we deduce

( • 5 ) ( • 5 ) ≥ (6∕5)(5∕4) ≥ (6∕5)(5∕4) lrw( • 5 )∕2 .
As 6∕5 > √ 5∕2, for every integer we have:

lim →∞ sup lrw( )≤ ( )≥ ( ) ( ) ≥ √ 5 2 . ( 9
)

Linear NLC-width

In this section we prove that classes with bounded linear NLC-width (and hence classes of bounded linear rankwdith) are linearly -bounded, and if they are stable, then they are transduction equivalent to classes of bounded pathwidth. We prove the result using Simon's factorization forest theorem.

Simon's factorization forest theorem

A semigroup is an algebra with one associative binary operation, usually denoted as multiplication. An idempotent in a semigroup is an element with = . Given an alphabet Ω we denote by Ω + the semigroup of all non-empty finite words over Ω, with concatenation as product.

Fix an alphabet Ω and a semigroup morphism ℎ ∶ Ω + → , where is a finite semigroup. A factorization tree is an ordered rooted tree (that is: a rooted plane tree) in which each node is either a leaf labeled by a letter, or an internal node. The value of a node is the word obtained by reading the descendant leaves below from left to right. The value of a factorization tree is the value of the root of the tree. A factorization tree of a word ∈ Ω + is a factorization tree of value . The depth of the tree is defined as usual, with the convention that the depth of a single leaf is 1. A factorization tree is Ramseyan (for ℎ) if every node 1) is a leaf, or 2) has two children, or, 3) the values of its children are all mapped by ℎ to the same idempotent of . Theorem 4.1 (Simon's Factorization Forest Theorem [START_REF] Kufleitner | The height of factorization forests[END_REF][START_REF] Simon | Factorization forests of finite height[END_REF]). For every alphabet Ω, every finite semigroup , and every semigroup morphism ℎ ∶ Ω + → , every word ∈ Ω + has a Ramseyan factorization tree of depth at most 3| |.

The existence of an upper bound expressed only in terms of | | was first proved by Simon [START_REF] Simon | Factorization forests of finite height[END_REF]. The improved upper bound of 3| | is due to Kufleitner [START_REF] Kufleitner | The height of factorization forests[END_REF].

Application to classes with bounded linear NLC-width

In the following we consider the semigroup Γ on functions ∶ [ ] → [ ]. Obviously, ℎ ∶ Ω ( ) + → Γ induced by ℎ( ) = for ∈ Ω ( ) is a semigroup homomorphism (recall Definition 3.1). An idempotent of Γ is a function that satisfies that if ( ) = , then ( ) = . We call ∈ Ω ( ) + an idempotent if ℎ( ) is an idempotent in Γ .

For ∈ ( ) (recall Definition 3.2) and for a letter of and = define col ( ) as the color of the vertex in Ξ( ). Note that if ∈ ( ) then col ( ) = ℎ( )(col ( )). Fix ∈ ( ). According to Theorem 4.1, there exists an ordered rooted tree that is a Ramseyan factorization tree of for ℎ with depth at most 3|Γ |. For the rest of this section fix such a tree .

For a node of we denote by ̄ the value of , which is a subword of . Note that the leaves of are naturally identified with the letters of . If , are two nodes of , note that:

• is an ancestor of in if and only if ̄ is a subword of ̄ ,

• is to the left of in if and only if ̄ and ̄ are disjoint and ̄ appears before ̄ in ,

• is immediately to the left of in (meaning that they are consecutive children of a same node, with at the left of ) if and only if ̄ ̄ is a subword of .

For a word = 1 ⋯ (where the 's are letters), for a leaf of with ̄ = , and for 1 ≤ ≤ we define

recol , = -1 • ⋯ • 1 = ℎ( 1 ⋯ -1 ), eset ( ) = recol -1 , ( ).
Lemma 4.2. Let 1 , 2 be two leaves of such that the letters of ̄ 1 and ̄ 2 appear in this order in , let = 1 ∧ 2 be their least common ancestor in , and let 1 (resp. 2 ) be the children of that are ancestors of 1 and 2 , respectively. Then 1 and 2 are adjacent in Ξ( ) if

Now consider an internal node of and a 4-tuple

( 1 , 1 , 2 , 2 ) ∈ [ ] × 2 [ ] × [ ] × 2 [
] with 1 ∈ 2 and 2 ∉ 1 , such that at least one descendent 1 of is such that col ̄ ( 1 ) = 1 and eset ̄ ( 1 ) = 1 and at least one descendent 2 of is such that col ̄ ( 2 ) = 2 and eset ̄ ( 2 ) = 2 . We consider new intervals coming from the split of the into subintervals (we keep the interval , as well as the new intervals arising from the split): These subintervals are obtained by considering the children of in order. The subintervals are of three types:

• type (1) intervals subsume the intervals of consecutive children of with at least one descendant with col ̄ ( ) = 1 and eset ̄ ( ) = 1 , but no descendant with col ̄ ( ) = 2 and eset ̄ ( ) = 2 ;

• type (2) intervals subsume the intervals of consecutive children of with at least one descendant with col ̄ ( ) = 2 and eset ̄ ( ) = 2 , but no descendant with col ̄ ( ) = 1 and eset ̄ ( ) = 1 ;

• type (1 + 2) intervals contain the interval of a single child of with both a descendent 1 with col ̄ ( 1 ) = 1 and eset ̄ ( 1 ) = 1 and a descendent 2 with col ̄ ( 2 ) = 2 and eset ̄ ( 2 ) = 2 .

The division of into subintervals is done in such a way that no two consecutive subintervals are both of type (1) or both of type [START_REF] Alon | Ramsey-type theorems with forbidden subgraphs[END_REF]. Note that such a division into subintervals exists. Furthermore, for all new subintervals and ′ (obtained from the split of ) that are direct neighbors, we add a new interval , ′ subsuming the two intervals and ′ . This finishes the construction of the graph .

Assume that the number of subintervals into which we divided is . Then we can select, among the descendants of the distinct children of some vertices 1 , 1 , … , , (with ≥ ∕4) such that col ̄ ( ) = 1 , eset ̄ ( ) = 1 , col ̄ ( ) = 2 , and eset ̄ ( ) = 2 . We deduce from Lemma 4.4 applied to and 1 , 1 , … , , and the assumption that C excludes some semi-induced half-graph, that is divided into a bounded number of subintervals. Now, it is immediate from the definition of pathwidth as one less than the minimum clique number of an interval supergraph of that has bounded pathwidth (depending on the NLC-width of and the bound on the length of the largest semi-induced half-graph in ) as desired.

We now add colors to the vertices of (that will be used by the transduction to reconstruct the graph ). First, we assign each vertex representing an interval all associated 4-tuples ( 1 , 1 , 2 , 2 ). For each vertex we add the information col ̄ ( ) and 1 = eset ̄ ( ) for each predecessor of . Finally, recall that each split of into subintervals is into at most parts. We add additional colors to number these intervals (in their left-to-right order) as 1, … , .

Let us show how to reconstruct the edges of from the colored graph . Let , be vertices, let be their least common ancestor in and let and be the children of such that is a descendant of and such that is a descendant of . We aim to apply Lemma 4.2 to decode whether and are adjacent. The problem is that we do not know in what order and appear below . Assume first that and are not direct neighbors (this can be checked using the vertex representing the interval , ). Let 1 = col ̄ ( ), 1 = eset ̄ ( ), 2 = col ̄ ( ), and 2 = eset ̄ ( ). The values of col ̄ and eset ̄ for and are available from the predicates at these vertices. If 1 ∈ 2 and 2 ∈ 1 , then the order of and does not matter, and we can conclude that and are adjacent. Similarly, if 1 ∉ 2 and 2 ∉ 1 then and are non-adjacent.

In the last case, without loss of generality, we can assume 1 ∈ 2 and 2 ∉ 1 . Observe that in this case the two vertices and cannot belong to a same subinterval of . Then from the numbering marks associated to the subintervals that contain and we deduce which of and is smaller than the other and hence the we can derive the adjacency between and .

If and are direct neighbors we argue analogously, referring to the values of col ̄ , col ̄ , eset ̄ and eset ̄ , which are also known from the predicates at these vertices.

To conclude, observe that the above reconstruction can easily be done by a first-order formula.

From this we deduce.

Linear rankwidth

In this section we present a second proof for the result that classes with bounded linear rankwidth are linearly -bounded and thereby provide improved constants.

Notation

For sets , ⊆ ( ) we define ⊕ as the symmetric difference of and , that is, ∈ ⊕ if and only if ∈ ∪ but ∉ ∩ . For ∈ , we define > ∶= { ∶ > }, < ∶= { ∶ < } and ≤ ∶= { ∶ ≤ }. For ∈ we denote by ( ) the neighborhood of ∈ (where not included). We let < ( ) ∶= ( ) ∩ < and define similarly > and ≤ . For ⊆ ( )

we define ⊕ ( ) ∶= ⨁ ∈ ( ) and > ⊕ ( ) ∶= ⊕ ( ) ∩ > . Remark 5.1. If < ′ , then > ⊕ ( ) = > ⊕ ( ) implies > ′ ⊕ ( ) = > ′ ⊕ ( ).
For ∈ the closure of { > ( ) ∶ ≤ } under ⊕ is a vector space over ⊕ and scalar multiplication with 0 and 1, where 0 ⋅ = ∅ and 1 ⋅ = . For ∈ , we call an inclusion-minimal subset ⊆ ≤ a neighbor basis for > if for every ≤ there exists ′ ⊆ such that > ( ) = > ⊕ ( ′ ). In other words, is a neighbor basis for > if { > ( ) ∶ ∈ } forms a basis for the space spanned by { > ( ) ∶ ≤ }.

The following is immediate by the definition of linear rankwidth.

Remark 5.2. As has linear rankwidth at most , for every ∈ every neighbor basis for > has at most vertices.

Activity intervals and active basis

For ∈ we define the active basis at as the set of all vertices smaller or equal to , whose neighborhood in > is not in the vector space generated by the neighborhoods in > of smaller vertices, that is:

= { ≤ ∶ (∄ ⊆ < ) > ( ) = > ⊕ ( )}. (10)
Note that this is the lexicographically least neighborhood basis of > .

Remark 5.3. If the linear order of ( ) is given, the set of all neighborhood basis for ∈ ( ) can be computed in quadratic time, by iteratively considering in increasing order and maintaining the set of at most 2 neighborhoods in > .

To each ∈ we associate its activity interval defined as the interval [ , ( )] starting at and ending at the minimum vertex ( ) ≥ such that ∉ ( ) . Note that ( ) is well defined as we have max = ∅.

We extend the definitions of the activity intervals and of the function to all non-empty subsets of ( ) by

∶= ⋂ ∈ and ( ) = min ∈ ( ). (11)
Note that either

= ∅ or = [max , ( )]. We call a set active if | | > 1, that is, if max < ( ).
We call a vertex active if the singleton set { } is active.

For every ∈ , as ∉ ( ) , there exists a unique 0 ( ) ⊆ ( ) with

> ( ) ( ) = > ( ) ⊕ ( 0 ( )). (12)
According to [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF] and as ∉ ( ) we have 0 ( ) ⊆ < hence max 0 ( ) < . Moreover, ( ) ≥ by definition and, if 0 ( ) is a non-empty subset of ( ) then every vertex in 0 ( ) is such that ( ) > ( ) hence ( 0 ( )) > ( ). Altogether we have that if 0 ( ) ≠ ∅ then we have:

max 0 ( ) < ≤ ( ) < ( 0 ( )). (13)
Hence, in this case, the set 0 ( ) is active.

Remark 5.4. Assume that is an active set and let ∈ .

1. If ( ) > ( ), then ∈ ( ) .

2. If ( ) = ( ), then 0 ( ) ⊆ ( ) .

Proof. As is active we have = [max , ( )]. In particular, if ( ) > ( ) we have ( ) ∈ (since ≤ max ) thus ∈ ( ) . If ( ) = ( ), then by definition of 0 we have 0 ( ) ⊆ ( ) = ( ) .

The F-tree

We define a mapping extending 0 , that will define a rooted tree on the set consisting of all active sets, all singleton sets { } for ∈ ( ), and ∅ (which will be the root of the tree and the unique fixed point of ). Before we define we make one more observation. Lemma 5.5. Let , ∈ ( ) be active. If ( ) = ( ), then = .

Proof. Let = ( ) = ( ) and let ′ be the predecessor of in the linear order. Assume for contradiction that ≠ . By definition of 0 we have > ( ) = > ( 0 ( )) and > ( ) = > ( 0 ( )). We have > ′ ( ) ≠ > ′ ( 0 ( )) as otherwise ( ) ≤ ′ . As > ′ ( ) ⊕ > ( ) ⊆ { } and > ′ ( 0 ( )) ⊕ > ( 0 ( )) ⊆ { }, we have > ′ ( 0 ( )) = > ′ ( ) ⊕ { }. Similarly, we have > ′ ( 0 ( )) = > ′ ( ) ⊕ { }. Assume without loss of generality that < . Then > ′ ( ) = > ′ ({ }) ⊕ > ′ ( 0 ( )) ⊕ > ′ ( 0 ( )). As max({ } ∪ 0 ( ) ∪ 0 ( )) < we deduce that ( ) ≤ ′ , contradicting ( ) = .

Corollary 5.1. For each active set ⊆ ( ) there exists exactly one ∈ with ( ) = ( ).

The mapping ∶ → is defined as

( ) = ⎧ ⎪ ⎨ ⎪ ⎩ ∅ if = ∅, ⊕ { } ⊕ 0 ( ) for the unique ∈ with ( ) = ( ), otherwise. ( 14
)
Remark 5.6. If the linear order on ( ) is given then -mapping on can be computed in quadratic time. Indeed, the computation of all the active basis can be done in quadratic time, and each time a vertex leaves the current active basis one can compute 0 ( ) by checking the space of the 2 neighborhoods in > generated by . (Note that

| | ≤ 2 | ( )|.)
The following lemma shows for every active set , either ( ) = ∅ or ( ) is active, and thus ( ) ∈ and is well defined. Furthermore, the lemma shows that ( ) ⊃ .

Lemma 5.7. Let ∈ . Then ( ) ⊆ ( ) and furthermore, either ( ) = ∅, or max ( ) ≤ max < ( ) < ( ( )) and hence ( ) is active.

Proof. The statement is obvious if = ∅. For = { }, the statement is immediate from the definition of 0 ( ) and [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF]. For all other ∈ , according to remark 5.4 we have for each ∈ either ∈ ( ) if ( ) > ( ), or 0 ( ) ⊆ ( ) if ( ) = ( ). This implies ( ) ⊆ ( ) . Finally, if ( ) ≠ ∅, then max ( ) ≤ max < ( ) < ( ( )) follows from the fact that these inequalities hold for all ∈ with ( ) > ( ) and for 0 ( ) for the unique ∈ with ( ) = ( ) according to [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF].

The mapping guides the process of iterative referencing and ensures that, for an active set , if ≥ ( ), then the set > ⊕ ( ) can be rewritten as > ⊕ ( ( )). This property is stated in the next lemma. Lemma 5.8. Let ∈ ⧵ {∅} and let ∈ ( ). If > ( ), then

∈ ⊕ ( ) ⇔ ∈ ⊕ ( ( )).
Proof. If = { } for ∈ ( ), then this follows from [START_REF] Courcelle | Handle-rewriting hypergraph grammars[END_REF]. Otherwise, is an active set. Let = ( ) and let ∈ be the unique element with ( ) = . Then we have > ⊕ ( 0 ( )) = > ⊕ ( ), and hence

> ⊕ ( ( )) = > ⊕ ({ }) ⊕ > ⊕ ( ( ) ⊕ { }) = > ⊕ ( 0 ( )) ⊕ > ⊕ ( ( ) ⊕ { }) = > ⊕ ( ).
This lemma can be applied repeatedly to , ( ), etc. until ( ) = ∅, or until for some given ∈ ( ) we have ( ( )) ≥ . This justifies to introduce, for distinct vertices and the value

( , ) ∶= min{ ≥ 0 ∶ ({ }) = ∅ or ({ }) ≠ ∅ and ∈ ({ }) }, (15)
where we let 0 ( ) = by convention. As a direct consequence of the previous lemma we have Corollary 5.2. For < in ( ) we have

{ , } ∈ ( ) ⟺ ∈ ⊕ ( ( , ) ({ })).
Proof. We claim that for all 0 ≤ ≤ ( , ) and < , and are adjacent if and only if ∈ ⊕ ( ({ })). We proceed by induction on . If = 0, then the statement is { , } ∈ ( ) ⇔ ∈ ⊕ ( ), which trivially holds. Assume ≥ 1. By Lemma 5.7 we have > ( -1 ({ })). Moreover, -1 ({ }) ∈ ⧵ {∅}. Hence by Lemma 5.8 we have ∈

-1 ({ }) ⟺ ∈ ({ }). As { , } ∈ ( ) ⟺ ∈ ⊕ ( -1 ({ })) by induction hypothesis, we deduce { , } ∈ ( ) ⟺ ∈ ⊕ ( ({ })).
The monotonicity property of (i.e. the property ( ( )) > ( ) if ( ) ≠ ∅) implies that defines a rooted tree, the -tree, with vertex set , root ∅ and edges { , ( )}. Here the monotonicity guarantees that the graph is acyclic and it is connected because ∅ is the only fixed point of . The following lemma shows that the -tree has bounded height. Recall that denotes the linear rankwidth of . Lemma 5.9. For every ∈ we have +1 ( ) = ∅.

Proof. If = ∅, the statement is obvious, so assume ≠ ∅. It is sufficient to prove that for every active set we have ( ) = ∅, as this implies +1 ({ }) = ∅ also for all ∈ ( ). Let be an active set and let ∈ . Then every ∈ is in , so ⊆ . Assume ≥ 1 is such that ( ) ≠ ∅. As max ( ) ≤ max and ( ( )) > ( ) by Lemma 5.7, we get max ( ) ≤ max ≤ < ( ) ≤ ( -1 ( )) < ( ( )).

As ( ( )) = min ∈ ( ) ( ), we have ( ) ⊆ . Hence, considering the sequence , ( ), … , ( ), each iteration of removes the unique element with minimum value. It follows that the union of the sets has cardinality at least + 1. As | | ≤ , we have < and hence ( ) = ∅.

Conclusion, further works, and open problems

In this paper, several aspects of classes with bounded linear-rankwidth have been studied, both from (structural) graph theoretical and the model theoretical points of view. On the one hand, it appeared that graphs with bounded linear rankwidth do not form a "prime" class, in the sense that they can be further decomposed/covered using pieces in classes with bounded embedded shrubdepth. As an immediate corollary we obtained that classes with bounded linear rankwidth are linearly -bounded. Of course, the ∕ bound obtained in Theorem 5.17 is most probably very far from being optimal.

On the other hand, considering how graphs with linear rank-width at most are encoded in a linear order or in a graph with bounded pathwidth with marginal "quantifier-free" use of a compatible linear order improved our understanding of this class in the first-order transduction framework.

Classes with bounded rankwidth seem to be much more complex than expected and no simple extension of the results obtained from classes with bounded linear rankwidth seems to hold. In particular, these classes seem to be "prime" in the sense that you cannot even partition the vertex set into a bounded number of parts, each inducing a graph is a simple hereditary class like the class of cographs (see Corollary 3.2). However, the following conjecture seems reasonable to us. Proof. Clearly 1 ⇒ 2 ⇒ 3. For 3 ⇒ 4, let be an integer and consider a depth-cover  of ∈ C with linear rankwidth at most . If C excludes some semi-induced half-graph we deduce by Theorem 4.6 that each ∈  induces a subgraph that is a fixed transduction of a graph with pathwidth at most ( ), hence, of a class that has depthcovers with bounded shrubdepth. Considering the intersection of the two covers, we get that C has depth-covers with bounded shrubdepth, hence, has structurally bounded expansion. Thus 3 ⇒ 4. Finally, 4 ⇒ 1 is implied by Theorem 2.5.

The next example illustrates again the concept of simple transductions and as a side product will provide us with some examples of classes of graphs admitting low linear rankwidth covers. Example 6.3. We consider the following graph classes, introduced in [START_REF] Lozin | Minimal classes of graphs of unbounded clique-width[END_REF]. Let , be integers. The graph , has vertex set = { , ∶ ( , ) ∈ [ ] × [ ]}. In this graph, two vertices , and ′ , ′ with ≤ ′ are adjacent if ′ = + 1 and ′ ≤ . The graph ̃ , is obtained from

, by adding all the edges between vertices having same first index (that is between , and , ′ for every ∈ [ ] and all distinct , ′ ∈ [ ].

First note that for fixed ∈ ℕ the classes H = { , ∶ ∈ ℕ} and H = { ̃ , ∶ ∈ ℕ} have bounded linear rank-width as they can be obtained as interpretations of -colored linear orders: we consider the linear order on { , ∶ ( , ) ∈ [ ] × [ ]} defined by , < ′ , ′ if < ′ or ( = ′ ) and ( < ′ ). We color , by color . Then the graphs in H are obtained by the interpretation stating that < are adjacent if the color of is one less than the color of , and if there is no between and with the same color as . The graphs in H are obtained by further adding all the edges between vertices with same color.

Following the lines of [START_REF] Kwon | Graph-theoretic concepts in computer science[END_REF]Theorem 9] we deduce from Example 6.3: Proposition 6.4. The class of unit interval graphs and the class of bipartite permutation graphs admit low linear rank-width colorings.

As we have shown above, classes with low linear rankwidth covers generalize structurally bounded expansion classes. Among the first problems to be solved on these class, two arise very naturally: Problem 6.5. Is it true that every first-order transduction of a class with low linear rankwidth covers has again low linear rankwidth covers?

As a stronger form of this problem, one can also wonder whether classes with low linear rankwidth covers enjoy a form of quantifier elimination, as structurally bounded expansion class do. Problem 6.6. Is it true that every class with low linear-rankwidth covers is monadically NIP? Note that it is easily checked that a positive answer to Problem 6.5 would imply a positive answer to Problem 6.6.

  monadic stability first-order transduction structurally bounded expansion 2010 MSC: 05C75 (Structural characterization of families of graphs), 05C15 (Coloring of graphs and hypergraphs), 05C50 (Graphs and linear algebra), 03C13 (Finite structures), 03C45 (Classification theory, stability and related concepts)

2 )

 2 For a class C with bounded linear rankwidth the following conditions are equivalent: a) C is stable, b) C excludes some half-graph as a semi-induced subgraph, c) C is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers. ⋆ This paper is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 810115 -DYNASNET).

Figure 1 :

 1 Figure 1: Inclusion map of graph classes. Some examples of classes are given in brackets.

  tw( ) = min{ ( ) -1 ∶ chordal and ⊇ }, pw( ) = min{ ( ) -1 ∶ interval graph and ⊇ }, td( ) = min{ ( ) ∶ trivially perfect and ⊇ }.

Figure 2 :

 2 Figure 2: The half-graph

Corollary 2 . 1 .

 21 Let C be a monotone class of graphs. Then the following are equivalent. 1. C is nowhere dense, 2. C is stable, 3. C is monadically stable, 4. C is NIP, 5. C is monadically NIP, 6. C has low VC-density, 7. C has monadically low VC-density.

  a finite set of unary relation symbols. If, for every in D there exists a lift + of some structure ∈ C such that = ( + ) we write C / / / / D, and we write C / / / / D if there exists such that C / / / / D. In this case we call the class D a transduction of C . The classes C and D are called transduction-equivalent if C / / / / D and D / / / / C .

Lemma 2 . 15 .

 215 Every class with bounded shrubdepth has bounded c-chromatic number.

2. C has bounded cliquewidth, 3 .

 3 C has bounded NLC-width, 4. Y ≤ / / / / C , as well as the following: 1. C has bounded linear rankwidth, 2. C has bounded linear cliquewidth, 3. C has bounded linear NLC-width, 4. C has bounded neighborhood-width, 5. L ≤ / / / / C .

Figure 4 : 1 . 3 . 4 . 3 . 1 .

 413431 Figure 4: Rank decomposition of ( • ) ⊕ 1 from the rank decompositions of ⊕ 1 and ⊕ 1 .

Conjecture 6 . 1 .Theorem 6 . 2 .

 6162 Let C be a class of graphs of bounded rankwidth. Then C has structurally bounded treewidth if and only if C is stable. We believe that our study of classes with bounded linear rankwidth might open the perspective to study classes admitting low linear rankwidth covers. Let us elaborate on this. As a consequence of Theorem 4.6 we have the following: Let C be a class with low linear rankwidth covers. Then the following are equivalent: 1. C is monadically stable, 2. C is stable, 3. C excludes a semi-induced half-graph, 4. C has structurally bounded expansion.

1 .

 1 C has bounded expansion if and only if there exists a function ∶ ℕ → ℕ such that for every graph , if the A class is monadically stable if and only if it is both monadically NIP and stable; it is structurally nowhere dense if and only if it is both monadically NIP and structurally weakly sparse. No class is currently known, which is monadically stable but not structurally nowhere dense.

	Monadically NIP
	Monadically stable	Stable
	Structurally	Structurally Structurally
	nowhere dense	weakly sparse weakly sparse
	Figure 3:

≤ -subdivision of belongs to C then the average degree of is at most ( ) (for all non-negative integers ). 2. C is nowhere dense if and only if there exists a function ∶ ℕ → ℕ such that the class C contains no ≤subdivision of a complete graphs of order greater than ( ) (for all non-negative integers ). Corollary 2.3. Let C be a monadically NIP class. Then C is nowhere dense if and only if it is weakly sparse. Proof. If C is nowhere dense, then there exists a number such that no graph in C contains a ≤ 1-subdivision of a complete graph as a subgraph. In particular, no graph in C contains ,( 2 ) as a subgraph, hence C is weakly sparse.

  Theorem 4.6. Let C be a class of graphs with linear rankwidth at most . Then the following are equivalent:

	1. C is stable,
	2. C is monadically stable,
	3. C is sparsifiable,
	4. C has 2-covers with bounded shrubdepth,
	5. C has structurally bounded expansion,
	6. C is a transduction of a class with bounded pathwidth,
	7. C excludes some semi-induced half-graph.

Acknowledgments

The authors express their gratitude to the referee for his careful reading and valuable comments.

Supported by CE-ITI P202/12/G061 of GAČR 2 Supported by by the European Associated Laboratory (LEA STRUCO). 3 Supported by Deutsche Forschungsgemeinschaft (DFG) -"Graph Classes of Bounded Shrubdepth" Projekt number 420419861 J. Nešetřil et al.:

• 1 is not immediately to the left of 2 in and col ̄ 1 ( 1 ) ∈ eset ̄ ( 2 ), • or 1 is immediately to the left of 2 in and col ̄ 1 ( 1 ) ∈ eset ̄ 2 ( 2 ). Proof. Assume that 1 is immediately to the left of 2 in , and let ̄ = ̄ 1 ̄ 2 ′ . Let ̄ 2 = 1 … with = ̄ 2 . The color of 1 in Ξ( ̄ 1 ) is the same as in Ξ( ̄ 1 ) -that is col ̄ 1 ( 1 ) -as ̄ 1 is in ̄ 1 . The color of 1 at the point where

). Thus 1 and 2 are adjacent if col ̄ 1 ( 1 ) ∈ eset ̄ 2 ( 2 ). Now assume that 1 is not immediately to the left of 2 in , and let ̄ = ̄ 1 ′ ̄ 2 ′′ . In this case has more than two children, hence, all its children have the same ℎ-value, which is an idempotent. In particular, ℎ( ′ ) = ℎ( ̄ 1 ′ ). The color of 1 at the point where 2 is created is

). Thus 1 and 2 are adjacent if col ̄ 1 ( 1 ) ∈ eset ̄ ( 2 ). We can now prove our first main theorem. Theorem 4.3. Let ( ) = ( 2 +1 ) 3 and ( ) = 3 . Every graph with linear NLC-width at most can be vertex partitioned into ( ) cographs with a cotree of depth at most ( ).

Proof. Let be a coloring of the nodes of with color in {1, 2} such that two consecutive children of a node have a different color. For a letter of , color by the vector of values ( ( ), col ̄ ( ), eset ̄ ( )) for ancestor of (ordered in increasing distance to the root). (This gives a vector of at most 3|Γ | triples.) Consider a monochromatic subset of vertices . Let 1 , 2 be distinct vertices of , let = 1 ∧ 2 , and let 1 and 2 be the children of that are ancestors of 1 and 2 , respectively. As is monochromatic and as 1 and 2 are at the same height in we have in particular ( 1 ) = ( 2 ) hence 1 and 2 are not consecutive children of . As is monochromatic we also have

. Hence, we can label the internal nodes of with 0 and 1 in such a way that two vertices in are adjacent if and only if the label at their least common ancestor in is 1. In particular, induces a cograph with cotree height at most ( ) = 3|Γ | = 3 . The colors we used are vectors of at most ( ) triples. Each triple consists of ( ) (2 possible values), col ̄ ( ) ( possible values) and eset ̄ ( ) (2 possible values). Altogether, this gives at most (2 2 ) ( ) = ( ) colors. Towards the goal of characterizing stable classes of bounded linear NLC-width, we observe that the following configuration leads to semi-induced half-graphs. We call semi-induced in if we can find in vertices 1 , … , and 1 , … , such that { , } ∈ ( ) if and only if 1 ≤ ≤ ≤ . Observe that we make no statement about edges between the or between the . Lemma 4.4. Assume there exist a node and leaves 1 , 1 , 2 , 2 , … , , of (in left-right order) such that is the least common ancestor of each pair of these leaves, and that there exist , ∈ [ ] and , ⊆ [ ] with ∈ , ∉ , and, for each

, and eset ̄ ( ) = . Then Ξ( ) contains a semi-induced half-graph of order at least ⌊ ∕3⌋.

Proof. By taking at least a third of the indices we can assume that no two letters appear in consecutive children of . Then it follows directly from Lemma 4.2 that these vertices semi-induce a half-graph. Proof. We first construct an interval graph , where each node of corresponds to an interval . The descendent relation of is the containment relation in the set of intervals.

For distinct vertices , , let ∧ denote the greatest common ancestor of and in the -tree, i.e. the first common vertex on the paths to the root. If ∧ is not the root of the -tree then there exist and such that ∧ = ({ }) = ({ }) ≠ ∅, hence both and belong to ∧ . Thus we have ( ∧ ) > and ( ∧ ) > . In other words, we have ( , ) ≤ and ( , ) ≤ .

The activity interval graph

Let be the intersection graph of the intervals for ∈ ( ). Note that we may identify ( ) with ( ) as min = for all ( ).

Lemma 5.10. In the intersection graph of the intervals at most + 2 intervals intersect in each point (hence

Proof. Consider any vertex with ∈ for some . The case ∈ gives a maximum of intervals intersecting in . Otherwise = ( ), which gives at most two possibilities for : either is inactive (and = ), or is active (and is uniquely determined, according to Lemma 5.5). Thus at most + 2 intervals intersect at point .

As mentioned in the proof of the above lemma, every clique of contains at most one inactive vertex. It follows that there is a coloring ∶ ( ) → [ + 2] with the following properties:

(1) for every ∈ ( ) we have ( ) = + 2 if and only if is inactive;

(2) for all distinct , ∈ ( ) we have

We extend this coloring to sets as follows: for ⊆ ( ) we let

This coloring allows to define, for each ∈ ( ) Class( ) ∶= ( ), Γ( ({ })), … , Γ( ({ })) ,

NCol( ) ∶= { ( ) ∶ ∈ ( ) and ∈ }

Note that all with ∈ define a clique of (because all contain ) and hence have distinct -colors.

Lemma 5.11. Let ∈ ( ). Every ∈ can be defined as the maximum vertex ≤ with ( ) = ( ).

Proof. By assumption we have ≤ . Assume towards a contradiction that there exists ∈ ( ) with < ≤ and ( ) = ( ). As ∈ we have ( ) > , hence ∈ . It follows that ∩ ≠ ∅, in contradiction to ( ) = ( ).

Towards the aim of bounding the number of graphs of linear rankwidth at most , we give a bound on the number of colors that can appear. Lemma 5.12. Let ( ) ∶= 2(2 + 1)( + 1)! 2 ( +12 ) . The number of Class( ) for ∈ ( ) can be bounded by (2 + 1)( + 1)! 2 ( 2 ) and the number of pairs (Class( ), NCol( )) for ∈ ( ) can be bounded by ( ).

Proof. Let ∈ ( ). From the fact that ( ) = + 2 if and only if is inactive, that images by only contain active vertices, as well as from Lemma 5.7 we deduce:

• If ( ) = + 2, then there exists a linear order on [ + 1] colors such that for 1 ≤ ≤ , the set Γ( ( )) is a subset of the first + 1 -colors of [ + 1].

• If ( ) ≤ + 1, then there exists a linear order on

Thus the number of distinct Class( ) for ∈ ( ) is bounded by

Furthermore, the number of distinct NCol( ) for ∈ ( ) is at most 2 +1 .

Encoding the graph in the linear order

We first make use of Corollary 5.2 to encode by a first-order formula using only the newly added colors and the order < on ( ). More precisely, for ∈ ( ), let

ICol( ) ∶= { ( ) ∶ ∈ }.

Let  be the structure over signature Λ ∪ {<}, where Λ is the set of all colors of the form (Class( ), NCol( ), ICol( )), with the same elements as and < interpreted as in . Every element of  is equipped with the color (Class( ), NCol( ), ICol( )). The following lemma gives a new proof of the result of [START_REF] Colcombet | A combinatorial theorem for trees[END_REF].

Lemma 5.13.

There exists an ∃∀-first-order formula ( , ) over the vocabulary Λ ∪ {<} such that for all , ∈ ( )

Proof. By symmetry, we can assume that < . According to Corollary 5.2 for distinct , ∈ ( ) we have

Note that we can extract any color from Λ, i.e. we can define ( ) ∈ Γ( ( )) and ( ) ∈ ICol( ). For example, ( ) ∈ Γ( ({ })) is a big disjunction over all possible colorings Λ( ) = (Class( ), NCol( ), ICol( )) and Λ( ) = (Class( ), NCol( ), ICol( )) satisfying that Class( ) has in its first component an element from the th component of Class( ).

We first define formulas ( , ) such that for all , ∈ ( )

Let = Γ( ({ })). According to Lemma 5.11, for ∈ , the element of ({ }) ⊆ with color is the maximal element < such that ( ) = . The formula can express that < is maximal with ( ) = by ( < ) ∧ ( ( ) = ) ∧∀ (( > ) ∧ ( < ) → ( ) ≠ ). Here, for convenience, we use ( ) = as an atom. Note that ( , ) is a ∀-formula.

We now define formulas ( , ) such that for all , ∈ ( ) with < we have

Observe that ∈ ({ }) if and only if for every ∈ ({ }) we have ≤ , ∈ ICol( ) (i.e. there exists some with ( ) = and ∈ ) and there exists no with < ≤ with ( ) = (hence min ≤ , which implies that and intersects thus = as ( ) = ( )). We restrict ourselves to the case < and obtain

Then ( , ) for < is the minimum integer such that ({ }) = ∅, or ∈ ({ }) and this is easy to state as a ∀formula. Finally, if we have determined ( , ), with the help of the formulas we can determine whether { , } ∈ ( ) as in the proof of Corollary 5.2 by existentially quantifying the elements of ({ }), 2 ({ }), … , ( , ) ({ }) and expressing whether ∈ ⊕ ( ( , ) ({ })). Indeed, for every ∈ ( , ) ({ }) we have ∈ ( , ) ({ }) ⊆ , hence the adjacency of and is encoded in NCol( ).

This information can hence be retrieved by an ∃∀-formula, as claimed.

Lemma 5.14. Let ′ ( ) ∶= (2 + 1)( + 1)! 2 ( 2 ) 3 +1 . The number of triples (Class( ), NCol( ), ICol( )) for ∈ ( ) can be bounded by ′ ( ).

Proof. By Lemma 5.12, the number of distinct Class( ) for ∈ ( ) is bounded by (2 + 1)( + 1)! 2 ( 2 ) . The number of pairs (NCol( ), ICol( )) is at most 3 +1 (for each color in [ + 1] either ∉ ICol( ) or ∈ ICol( ) ⧵ NCol( ) or ∈ NCol( )).

As a corollary we conclude an upper bound on the number of graphs of bounded linear rankwidth.

Partition into cographs

Theorem 5.17. Let ( ) = 2(2 + 1)( + 1)! 2 ( +1 2 ) . The -chromatic number of every graph (that is the minimum order of a partition of ( ) where each part induces a cograph) is bounded by (lrw( )). Hence

Proof. Let ∼ hold if and only if Class( ) = Class( ) and NCol( ) = NCol( ). As proved in Lemma 5.12 there are at most ( ) equivalence classes for the relation ∼.

Let be an equivalence class for ∼, and let , be distinct elements in . Let = ( , ) and let = ( , ).

and ∈ ({ }) we deduce that ({ }) and ({ }) are both included in . As the vertices of a given color in are uniquely determined we deduce ({ }) = ({ }). Similarly, we argue that ({ }) = ({ }). It follows that ({ }) = ({ }) = ∧ . Hence, if ∧ = ∧ for , ∈ , then we have ∧ = ({ }) = ({ }). As NCol( ) = NCol( ), we deduce that for all , ∈ with ∧ = ∧ we have ∈ ⊕ ( ({ })) or for all , ∈ with ∧ = ∧ we have ∉ ⊕ ( ({ })). Then it follows from Corollary 5.2 that at each inner vertex of on we either define a join or a union. Hence, [ ] is a cograph with cotree restricted to of height at most + 2.

Remark 5.18. The partition can be computed in quadratic time if the ordering of the vertex set is given.

The function ( ) is most probably far from being optimal. This naturally leads to the following question.

Remark 5.20. One may wonder whether bounding ( ) by an affine function of ( ) could decrease the coefficient of ( ). In other words, is the ratio ∕ be asymptotically much smaller (as → ∞) than its supremum? Note that if lrw( ) = and ∈ ℕ, then the graph obtained as the join of copies of satisfies lrw( ) ≤ + 1, ( ) = ( ) and ( ) = ( ). Thus